Chapter16 - Recurrance relations

Ex16.14 Pg 536

In [1]:
a=[]#
a.append(1)#  #initial condition
a.append(2)#  #initial condition
print 'for recurrence relation a(n)=5*a(n-1)-4*a(n-2)+n**2' #this is a second order recurrence relation with constant coefficients.It is non homogenous because of the n**2
for n in range(2,4):
    a.append(5*a[n-1]-4*a[n-2]+n**2)
    print 'Value of a(%d) is: %d \n'%(n,a[n])

 
a=[]#
a.append(1)#  #initial condition
a.append(2)#  #initial condition
print 'for recurrence relation a(n)=2*a(n-1)*a(n-2)+n**2'  #this recurrence relation is not linear
for n in range(2,4):
    a.append(2*a[(n-1)]*a[(n-2)]+n**2)
    print 'Value of a(%d) is: %d \n'%(n,a[n])

 
a=[]#
a.append(1)#  #initial condition
a.append(2)#  #initial condition
print 'for recurrence relation a(n)=n*a(n-1)+3*a(n-2)'   #this is a homogenous linear second order recurrence relation without constant coefficients because the coefficient of a[n-1] is n,not a constant
for n in range(2,4):
    a.append(n*a[(n-1)]+3*a[(n-2)])
    print 'Value of a(%d) is: %d \n'%(n,a[n])


 
a=[]#
a.append(1)#  #initial condition
a.append(2)#  #initial condition
a.append(1)#  #initial condition
print 'for recurrence relation a(n)=2*a(n-1)+5*a(n-2)-6*a(n-3)' #this is a homogenous linear third order recurrence relation with constant coefficients.Thus we need three,not two,initial conditions to yield a unique solution of the recurrence relation
for n in range(2,4):
    a.append(2*a[(n-1)]+5*a[(n-2)]-6*a[(n-3)])
    print 'Value of a(%d) is: %d \n'%(n,a[n])

for recurrence relation a(n)=5*a(n-1)-4*a(n-2)+n**2
Value of a(2) is: 10 

Value of a(3) is: 51 

for recurrence relation a(n)=2*a(n-1)*a(n-2)+n**2
Value of a(2) is: 8 

Value of a(3) is: 41 

for recurrence relation a(n)=n*a(n-1)+3*a(n-2)
Value of a(2) is: 7 

Value of a(3) is: 27 

for recurrence relation a(n)=2*a(n-1)+5*a(n-2)-6*a(n-3)
Value of a(2) is: 1 

Value of a(3) is: 3

Ex16.15 Pg 539

In [2]:
from numpy import mat
from sympy import symbols, solve
print 'recurrence relation of Fibonacci numbers f[n]=f[n-1]+f[n-2]'  
x=symbols('x')
g=x**2-x-1
print 'characterstic equation of the recurrence relation is:',g
j=solve(g,x)#
print 'roots of the characterstic equation j1,j2 are :'
for x in j:
    print x,'\t',

print '\n'
print 'for general equation fn=Ar**n+Br**n,values of Aand B respectively are calculated as:'
print 'initial condition at n=0 and n=1 respectively are:'
f1=1#  
f2=1#  
#putting the values of f1 and f2 we get the equations to solve 

D=mat([[1.6180340, -0.618034],[(1.6180340)**2,  (-0.618034)**2]])#
K=mat([[1, 1]])
c=[]#
c=D/K#
A=c[0]
B=c[1]
print A, B
print 'thus the solution is f[n]=0.4472136*((1.618034)**n-(- 0.4472136)**n)]'

recurrence relation of Fibonacci numbers f[n]=f[n-1]+f[n-2]
characterstic equation of the recurrence relation is: x**2 - x - 1
roots of the characterstic equation j1,j2 are :
1/2 + sqrt(5)/2 	-sqrt(5)/2 + 1/2 	

for general equation fn=Ar**n+Br**n,values of Aand B respectively are calculated as:
initial condition at n=0 and n=1 respectively are:
[[ 1.618034 -0.618034]] [[ 2.61803403  0.38196603]]
thus the solution is f[n]=0.4472136*((1.618034)**n-(- 0.4472136)**n)]

Ex16.17 Pg 543

In [3]:
from numpy import mat
from sympy import symbols, solve
print 'The recurrence relation t[n]=4(t[n-1]-t[n-2])'
x=symbols('x')
g=x**2-4*x+4
print 'characterstic polynomial equation for the above recurrence relation : ',g 
j=solve(g, x)
print 'roots of the characterstic equation j1,j2 : '
for x in j:
    print x,'\t'
print ''
print 'the general solution is t[n]=n*2**n' 
print 'initial condition at n=0 and n=1 respectively are:'
t0=1#
t1=1#
#putting the values of t0 and t1 we get the equations to solve
D=mat([[1, 0],[2, 2]])
K=mat([[1, 1]])
from numpy.linalg import solve
c=solve(D,K)
for cc in c:
    print c,'\t',
print ''
D=mat([[1, 0],[2, 2]])
K=mat([[1, 1]])
c=D/K#
c1=c[0]
c2=c[1]
print 'thus the solution is t{n}=2*n-n*2**(n-1)'

The recurrence relation t[n]=4(t[n-1]-t[n-2])
characterstic polynomial equation for the above recurrence relation :  x**2 - 4*x + 4
roots of the characterstic equation j1,j2 : 
2 	

the general solution is t[n]=n*2**n
initial condition at n=0 and n=1 respectively are:
[[ 1.   1. ]
 [-0.5 -0.5]] 	[[ 1.   1. ]
 [-0.5 -0.5]] 	
thus the solution is t{n}=2*n-n*2**(n-1)

Ex16.18 Pg 544

In [4]:
from numpy import mat
from sympy import symbols, solve
print 'The recurrence relation a[n]=2*a[n-1]-3a[n-2]'
x=symbols('x')
g=x**2-2*x-3
print 'characterstic polynomial equation for the above recurrence relation : ',g 
from sympy import solve
j=solve(g, x)#
print 'roots of the characterstic equation j1,j2 : '
for x in j:
    print x,'\t',
print ""
print 'the general solution is a[n]=c1*3**n+c2*(-1)**n' 
print 'initial condition at n=0 and n=1 respectively are:'
#putting the values of t0 and t1 we get the equations to solve
a0=1#
a1=2#
D=mat([[1, 1],[3, -1]])
K=mat([[1, 2]])
c=D/K#
c1=c[0]
c2=c[1]
print c1, c2
print 'thus the solution is a[n]=0.75*(3**n)+0.25*(1**n)'

The recurrence relation a[n]=2*a[n-1]-3a[n-2]
characterstic polynomial equation for the above recurrence relation :  x**2 - 2*x - 3
roots of the characterstic equation j1,j2 : 
-1 	3 	
the general solution is a[n]=c1*3**n+c2*(-1)**n
initial condition at n=0 and n=1 respectively are:
[[1 0]] [[ 3 -1]]
thus the solution is a[n]=0.75*(3**n)+0.25*(1**n)

Ex16.19 Pg 556

In [5]:
from numpy import mat
from sympy import symbols, solve
print 'The recurrence relation a[n]=11*a[n-1]-39*a[n-2]+45*a[n-3]'
x=symbols('x')
g=x**3-11*x**2+39*x-45
print 'characterstic polynomial equation for the above recurrence relation : ',g 
j=solve(g, x)
print 'roots of the characterstic equation j1,j2 : '
for x in j:
    print x,'\t',
print ''
print 'hence the general solution is:a[n]=c1*(3**n)+c2*n*(3**n)+c3*(5**n)'
print 'initial condition at n=0 and n=1 respectively are:'
#putting the values of t0 and t1 we get the equations to solve
a0=5#
a1=11#
a2=25#
D=mat([[1, 0 ,1],[3, 3, 5],[9, 18, 25]])
K=mat([[5, 11, 25]])
c=D/K#
c1=c[0]
c2=c[1]
c3=c[2]
print c1, c2, c3
print 'thus the solution is a[n]=(4-2*n)*(3**n)+5**n'

The recurrence relation a[n]=11*a[n-1]-39*a[n-2]+45*a[n-3]
characterstic polynomial equation for the above recurrence relation :  x**3 - 11*x**2 + 39*x - 45
roots of the characterstic equation j1,j2 : 
3 	5 	
hence the general solution is:a[n]=c1*(3**n)+c2*n*(3**n)+c3*(5**n)
initial condition at n=0 and n=1 respectively are:
[[0 0 0]] [[0 0 0]] [[1 1 1]]
thus the solution is a[n]=(4-2*n)*(3**n)+5**n