MODULE III
DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS
DISCRETE NUMERIC FUNCTIONS
A discrete numeric function is a function whose domain is the set of natural numbers and whose range is the set of real numbers. Let a be a discrete numeric function , it's value is a(0) , a(1),...... a(r)...... at the points ( 0,1,2,3...... r...... ) and is denoted by a0, a1,a2...... ar...... It may also be called sequence a0,a1,a2...... ar...... an and is denoted by { an} or (an)
SUM AND PRODUCT OF TWO NUMERIC FUNCTIONS
Let a and b be two numeric functions then the sum of two numeric functions is denoted a + b and another numeric function c such that cr = ar + br . The product of two functions is denoted by ab and another numeric function d such that dr = ar.br .
CONVOLUTION
The convolution of two numeric functions a and b is denoted by a * b and another numeric function c defined by cr = a0 br + a1 br-1 +...... + ar b0
r
= ∑ ak br-k
k=0
GENERATING FUNCTIONS
Consider a sequence ( a 0 ,a1,a2...... ar...... ) . This sequence may be represented by an infinite series a0 + a1 x + a2 x2 +...... +ar xr +...... +an xn . Where x is a formal variable and coefficient of xr is ar of the sequence. This sequence is called the generating function of the given sequence and is denoted by A(x).
A(x) = a0 + a1 x + a2 x2 +...... +ar xr +...... +an xn
Examples
1.Consider the sequence ( 30, 31 , 32...... 3r...... ) . Find its generating function ?
Soln:
Generating function is
A(x) = a0 + a1 x + a2 x2 +...... +ar xr +...... +an xn
= 30 +31 x +32 x2 +......
= 1 +3x +9x2 +......
= ( 1- 3x)-1
= 1
1-3x
2 .Find the discrete numeric function corresponding to the generating function is
A(x) = x
(1-x)2
Soln:
A(x) = x
(1-x)2
= x( 1-x)-2
= x( 1 +2x +3x2 +...... )
= x +2x2 + 3x3 +......
ar = r , r = 0,1,2......
3. Find the generating function for the sequence ( 0x 50, 1 x 51 , 2 x 52...... ).
Soln:
Generating function is
A (x) = a0 + a1 x + a2 x2 +...... +arxr +...... +an xn
= 0x50 +(1x51 )x +(2 x52 )x2 +......
= 5x +2 (52 x2 )+ 3( 53 x3) +......
= 5x ( 1 + 2 (5x)+ 3( 5x) 2 +...... )
= 5x( 1-5x)-2
= 5x
(1-5x)2
4 Find the discrete numeric function corresponding to the generating function is
A(x) = 1
1-x3
Soln:
A(x) = 1
1-x3
= (1-x3)-1
= 1 +x 3+ (x 3 )2 +......
a0 = 1
a1 = 0
a2 = 0
a3 = 1......
ie sequence is ( 1, 0, 0, 1 ...... )
Problems
1.Find the discrete numeric function corresponding to the generating function is
A(x) = 2
1-4x2
2. Find the discrete numeric function corresponding to the generating function is
A(x) = 1
5-6x+x2
RECURRENCE RELATION
The sequences can be defined by expressing the rth term ar explicitly as a function of r .This may also be represented by expressing nth term and in terms of some of the preceding terms with some additional informations.
Eg: consider ar = 3r this sequence may be defined by giving the recurrence relation an = 3an-1 with the additional information a0 = 1 .Such a relation is called a recurrence relation or difference equation. The additional informations are called the boundary conditions or initial conditions.
LINEAR RECURRENCE RELATION WITH CONSTANT COEFFICIENTS
A recurrence relation is of the form c0 an + c1 an-1 +...... + ck an-k = f(n) where c1 ,c2 ,...... are constants and the degree of the recurrence relation is k. An equation of the form c0 an + c1 an-1 +...... + ck an-k = 0 is called a homogeneous linear recurrence relation with constant coefficients.
Eg;
- an =3an-1 + 4 an-3. It is linear homogeneous with constant coefficients and degree is 3
- an = an-1 + an-2 +n +3 . it is linear non homogeneous with constant coefficients and degree is 2
SOLUTION OF LINEAR HOMOGENEOUS RECURRENCE RELATION WITH CONSTANT COEFFICIENTS
Consider the homogeneous recurrence relation with constant coefficients c0 an + c1 an-1 +...... + ck an-k = 0 and its degree is k .
Now consider the polynomial equation of degree k in some formal variable x as
c0 xk + c1xk-1 +...... + ck xk-k = 0
c0 xk + c1xk-1 +...... + ck = 0 This equation is called characteristic equation of the given recurrence relation and its roots are called characteristic roots.
Now following are the rules of finding the general solutions of given recurrence relation
DISTINCT ROOTS
If the equation has distinct roots r1, r2 ,...... rk then the general form of the solutions for homogeneous equation is an = b1r1n +b2 r2n+...... +bk rkn where b1, b2...... bk are constants and r1, r2...... are roots.
MULTIPLE ROOTS
If r is a root of the characteristic equation of mth order of a given recurrence relation with multiplicity m , then the general form of the solution is an = ( b1 + nb2 + n2b3+...... +nm-1 bm )rn
MIXED ROOTS
If the characteristic equation of a homogeneous recurrence relation of fourth order is
(r -2) (r-4) (r- 3)3 = 0 → r = 2,4, 3,3,3 then an = b12n+ b2 4n+ ( b3 +n b4+ n2b5) 3n.
Examples
- Solve the recurrence relation an = an-1 + 2 an-2 , n≥2 with the initial conditions a0 =0 ,a1= 1
Soln:
The given recurrence relation is
an = an-1 + 2 an-2
an - an-1 - 2 an-2 = 0
The characteristic equation is x2 – x – 2 =0
The characteristic roots are x = 2 ,-1
The solution is
an = b1 2n + b2 (-1)n
Given a0 = 0 and a1 =1
a0 = 0 → 0 = b1 + b2
a1 =1 → 1 = 2b1 - b2
b1 =1/3
b2 =-1/3
Solution is
an = 1/3( 2n ) - 1/3(-1)n
- Solve the recurrence relation an = 4(an-1 - an-2 ), n≥2 with the initial conditions a0 =1 ,
a1= 1
Soln:
The given recurrence relation is
an = 4(an-1 - an-2 )
an - 4an-1 + 4an-2 =0
The characteristic equation is x2 – 4x + 4 =0
The characteristic roots are x = 2 , 2
The solution is
an = ( b1 + nb2 )2n
Given a0 = 1and a1 =1
a0 = 1 → 1 = b1
a1 =1 → 1 = 2b1 + 2b2
b1 = 1
b2 = -1/2
Solution is
an = ( 1 - n/2 ) 2n
3. Solve the recurrence relation an – 8 an-1 + 21an-2 - 18 an-3 = 0 with the initial conditions a0 =0 , a1= 1, a2 = -1
Soln:
The given recurrence relation is an – 8 an-1 + 21an-2 - 18 an-3 = 0
The characteristic equation is x3 - 8 x2 + 21x – 18 =0
The characteristic roots are x = 2 , 3 , 3
The solution is
an = b1 2n + ( b2 + nb3)3n
Given a0 = 0 , a1 =1 and a2 = -1
a0 = 0 → 0 = b1 + b2
a1 =1 → 1 = 2b1 + 3b2 +3 b3
a2 = -1 → -1 = 4b1 + 9b2 +18b3
b1 = -7
b2 = 7
b3 = -2
Solution is
an = -7 2n + ( 7 – 2n)3n
Problems
- Solve the recurrence relation an +3 an-1 +3an-2 + an-3 = 0 with the initial conditions a0 =1, a1= -2, a2 = -1
- Solve the recurrence relation an = 6 an-1 -11an-2 + 6an-3 with the initial conditions a0 =2 , a1= 5, a2 = 15
- Solve the recurrence relation an = 3an-1 -3an-2 + an-3 with the initial conditions a0 =0 , a1= 3, a2 = 10
- Solve the recurrence relation ar -7 ar-2 + 6ar-3 =0 with the initial conditions a0 =8, a1= 6, a2 = 22
SOLUTION OF NON HOMOGENEOUS RECURRENCE RELATION WITH CONSTANT COEFFICIENTS
A non homogeneous recurrence relation with constant coefficients is of the form,
c0 an + c1 an-1 +...... + ck an-k = f(n)
...... (1)
Now the homogeneous relation,
c0 an + c1 an-1 +...... + ck an-k = 0
...... (2)
The general solution of equation (2) is denoted by an(h) and particular solution of (1) is denoted by an(p) then the general solution is,
an = an(h) + an(p)
NO / f(n) / an(p)1.
2.
3.
4. / bn ( if b is not a root of characteristic equation)
cn p(n) ( if c is not a root of the characteristic equation)
bn ( if b is a root of characteristic equation of multiplicity s )
cn p(n) ( if c is a root of the characteristic equation of multiplicity t) / A0 +A1n+...... Am nm
cn ( A0 +A1n+...... Am nm)
A0nsbn
nt( A0 +A1n+...... )cn
Examples
1.Find the general solution of the recurrence relation an = 6an-1 -9an-2 + f(n) where
f(n) = n2 2n
Soln:
The given recurrence relation is
an = 6an-1 -9an-2 + f(n)
an - 6an-1 + 9an-2 = n2 2n
General solution is
an = an(h) + an(p)
an - 6an-1 + 9an-2 = 0
The characteristic equation is x2 - 6x + 9 =0
The characteristic roots are x = 3 , 3
The solution is
an (h) = ( b1+ nb2 )3n
Here f(n) = n2 2n
an(p) = 2n(A0 + A1n+ A2 n2) where A0, A1, A2...... are constants
The recurrence relation is
an - 6an-1 + 9an-2 = n2 2n
2n(A0 + A1n+ A2 n2) - 6( 2n -1 (A0 + A1 (n -1)+ A2 (n -1)2) + 9( 2n-2 (A0 + A1 (n - 2)+ A2 (n -2)2) = n2 2n
Canceling 2n-2 we get,
4(A0 + A1n+ A2 n2) - 6( 2(A0 + A1 (n -1)+ A2 (n -1)2) + 9(A0 + A1 (n - 2)+ A2 (n -2)2) = 4 n2
Equating the coefficients of n2, n, constant we get ,
A0 =192
A1 = 48
A2 = 4
an(p) = 2n( 192 + 48n+ 4n2)
General solution is
an = an(h) + an(p)
an = ( b1+ nb2 )3n + 2n( 192 + 48n+ 4n2)
2. Find the general solution of the recurrence relation an = 6an-1 -9an-2 + f(n) where
f(n) = 3n
Soln:
The given recurrence relation is
an = 6an-1 -9an-2 + f(n)
an - 6an-1 + 9an-2 = 3n
General solution is
an = an(h) + an(p)
an - 6an-1 + 9an-2 = 0
The characteristic equation is x2 - 6x + 9 =0
The characteristic roots are x = 3 , 3
The solution is
an (h) = ( b1+ nb2 )3n
Here f(n) = 3n
an(p) = A0 n2 3n where A0 is constants
The recurrence relation is
an - 6an-1 + 9an-2 = 3n
(A0 n2 3n ) - 6( A0 (n -1)2 3n-1 ) + 9(A0 (n -2)2 3n-2 ) = 3n
Canceling 3n-2 we get,
9A0 n2 - 18A0 (n -1)2 + 9A0 (n -2)2 = 9
Equating constant terms we get ,
A0 = ½
an(p) = A0 n2 3n
= ½ n2 3n
General solution is
an = an(h) + an(p)
an = ( b1+ nb2 )3n + ½ n2 3n
3. Find the general solution of the recurrence relation an = 6an-1 -9an-2 + f(n) where f(n) = n2
Soln:
The given recurrence relation is
an = 6an-1 -9an-2 + f(n)
an - 6an-1 + 9an-2 = n2
General solution is
an = an(h) + an(p)
an - 6an-1 + 9an-2 = 0
The characteristic equation is x2 - 6x + 9 =0
The characteristic roots are x = 3 , 3
The solution is
an (h) = ( b1+ nb2 )3n
Here f(n) = n2
an(p) = 1n(A0 + A1n+ A2 n2) where A0, A1, A2...... are constants
The recurrence relation is
an - 6an-1 + 9an-2 = n2
(A0 + A1n+ A2 n2) - 6(A0 + A1 (n -1)+ A2 (n -1)2) + 9(A0 + A1 (n - 2)+ A2 (n -2)2) = n2
Equating the coefficients of n2, n, constant we get ,
A0 = 21/8
A1 = 3/2
A2 = 1/4
an(p) = 21/8+ 3/2n+ 1/4n2
General solution is
an = an(h) + an(p)
an = ( b1+ nb2 )3n + 21/8+ 3/2n+ 1/4n2
Problems
1. Find the general solution of the recurrence relation an - 5an-1 + 6an-2 = 1
2. Find the general solution of the recurrence relation an - 3 an-1 - 4an-2 = f(n) where f(n) = 3n
3. Find the general solution of the recurrence relation an - 4 an-1 + 4an-2 = f(n) where
f(n) = 2n
SOLUTION OF RECURRENCE RELATION USING GENERATING FUNCTIONS
Many recurrence relations can be solved using generating functions. We shall explain the method using some examples
Examples
1. Solve the recurrence relation an = 3an-1 + 2 for n≥1 , a0 = 1 using generating function.
Soln:
The given recurrence relation is
an = 3an-1 + 2 ...... (1)
Multiply throughout by xn
an xn = 3an-1 xn + 2xn
∞ ∞ ∞
∑ an xn = ∑ 3an-1 xn + ∑ 2xn
n=1 n=1 n=1 ...... (2)
Let A(x) be the generating function of the sequence an, then
∞
A(x) = ∑ an xn
n=0
∞
∑ an xn = A(x) – a0 =A(x) – 1
n= 1
∞ ∞
∑ 3an-1 xn = 3x ∑ an xn = 3x A(x)
n= 1 n= 0
∞ ∞
∑ 2 xn = 2x ∑ xn = 2x
n= 1 n= 0 1-x
Substitute these values in equation (2) we get
A(x) -1 = 3x A(x) + 2x
1-x
A(x) = 1+x
(1-3x) (1-x)
= A + B
1-3x 1-x
= 2 + -1
1-3x 1-x
= 2 - 1
1-3x 1-x
= 2(1-3x )-1 - (1-x )-1
= 2( 1+3x+...... ) - ( 1+x+...... )
an = 2.3n -1
2. Solve the recurrence relation an = 8an-1 + 10 n-1 for n≥1 , a0 = 1 , a1 = 9 using generating function.
Soln:
The given recurrence relation is
an = 8an-1 + 10 n-1 ...... (1)
Multiply throughout by xn
an xn = 8an-1 xn + 10n-1 xn
∞ ∞ ∞
∑ an xn =8∑ an-1 xn + ∑ 10n-1 xn
n=1 n=1 n=1 ...... (2)
Let A(x) be the generating function of the sequence an, then
∞
A(x) = ∑ an xn
n=0
∞
∑ an xn = A(x) – a0 =A(x) – 1
n= 1
∞ ∞
8∑ an-1 xn = 8x ∑ an xn = 8x A(x)
n= 1 n= 0
∞ ∞
∑ 10n-1 xn = x ∑ (10x )n = x
n= 1 n= 0 1- 10x
Substitute these values in equation (2) we get
A(x) -1 = 8x A(x) + x
1-10x
A(x) = 1 - 9x
(1-10x) (1- 8x)
= A + B
1-10x 1-8x
= ½ + ½
1-10x 1 - 8x
= ½ (1-10x )-1 + ½ (1-8x )-1
= ½ ( 1+10x+...... ) + ½ ( 1+8x+...... )
an = ½ (8n + 10n )
Problems
- Solve the recurrence relation an + 3an-1 - 4 an-2 =0 for n≥2 , a0 =3 , a1 = -2 using generating function.
- Solve the recurrence relation an - 5an-1 = 5n for n≥1 , a0 =1 using generating function.
**********************************************