Recurrence relation
By Gunisha
Cse-2
Roll no-2101920100119
Table of content
• Recurrence relation-definition
• Order of recurrence relation
• Degree of difference equation
• Linear recurrence relation
• Examples of linear recurrence relation
• Cases for finding homogeneous solution
• Examples
• Cases for finding particular solution
• Examples
• Finding total solution
• Examples
• references
definition
A recurrence relation is an equation that recursively defines a sequence
where the next term is a function of the previous terms (Expressing Fn as
some combination of Fi with i<n).
examples
ar+3 + 3ar+2 + 6ar+1 + 9ar = 0
yk+3 + 3yk+2 + 6yk+1 + 9yk = 0
Order of recurrence relation
• The order of the recurrence relation or difference equation is
defined to be the difference between the highest and lowest
subscripts of f(x) or ar=yk.
• Example1: The equation 13ar+20ar-1=0 is a first order
recurrence relation.
• Example2: The equation 8f (x) + 4f (x + 1) + 8f (x+2) = k (x)
Degree of difference equation
• The degree of a difference equation is defined to be the highest power of f (x) or
ar=yk
• Example1: The equation y3k+3+2y2k+2+2yk+1=0 has the degree 3, as the highest
power of yk is 3.
• Example2: The equation a4r+3a3r-1+6a2r-2+4ar-3 =0 has the degree 4, as the highest
power of ar is 4.
• Example3: The equation yk+3 +2yk+2 +4yk+1+2yk= k(x) has the degree 1, because
the highest power of yk is 1 and its order is 3.
• Example4: The equation f (x+2h) - 4f(x+h) +2f(x) = 0 has the degree1 and its
order is 2.
Linear recurrence relations
• A Recurrence Relations is called linear if its degree is one.
• The general form of linear recurrence relation with constant
coefficient is
• C0 yn+r+C1 yn+r-1+C2 yn+r-2+⋯+Cr yn=R (n)
• Where C0,C1,C2......Cn are constant and R (n) is same function
of independent variable n
These are some examples of linear recurrence
relations
Recurrence relations Initial values Solutions
Fn = Fn-1 + Fn-2 a1 = a2 = 1 Fibonacci number
Fn = Fn-1 + Fn-2 a1 = 1, a2 = 3 Lucas Number
Fn = Fn-2 + Fn-3 a1 = a2 = a3 = 1 Padovan sequence
Fn = 2Fn-1 + Fn-2 a1 = 0, a2 = 1 Pell number
Cases for solution of recurrence relation
• Case1: If the characteristic equation has n distinct real roots ∝1, ∝2, ∝3,....... ∝n.
• Thus, Linear Recurrence Relations with Constant Coefficientsare all solutions of
equation (i).
• Also, we have Linear Recurrence Relations with Constant Coefficientsare all
solutions of equation (i). The sums of solutions are also solutions.
• Hence, the homogeneous solutions of the difference equation are
• Linear Recurrence Relations with Constant Coefficients
Case2: If the characteristics equation has repeated real roots.
If ∝1=∝2, then (A1+A2 K) Linear Recurrence Relations with Constant
Coefficientsis also a solution.
If ∝1=∝2=∝3 then (A1+A2 K+A3 K2) Linear Recurrence Relations with
Constant Coefficientsis also a solution.
Similarly, if root ∝1 is repeated n times, then.
(A1+A2 K+A3 K2+......+An Kn-1) Linear Recurrence Relations
with Constant Coefficients
Case3: If the characteristics equation has one imaginary root.
If α+iβ is the root of the characteristics equation, then α-iβ is also the root, where α
and β are real.
Thus, (α+iβ)K and (α-iβ)K are solutions of the equations. This implies
(α+iβ)K A1+α-iβ)K A2
Is also a solution to the characteristics equation, where A1 and A2 are constants
which are to be determined.
Case4: If the characteristics equation has repeated imaginary roots.
When the characteristics equation has repeated imaginary roots,
(C1+C2 k) (α+iβ)K +(C3+C4 K)(α-iβ)K
Is the solution to the homogeneous equation.
Example 1
Solve the difference equation ar-3ar-1+2ar-2=0.
Solution: The characteristics equation is given by
s2-3s+2=0 or (s-1)(s-2)=0
⇒ s = 1, 2
Therefore, the homogeneous solution of the equation is given by
ar=C1r+C2.2r.
Example 2
Solve the difference equation yK-yK-1-yK-2=0.
Solution: The characteristics equation is s2-s-1=0
s=Linear Recurrence Relations with Constant Coefficients
Therefore, the homogeneous solution of the equation is
Linear Recurrence Relations with Constant Coefficients
Example 3
Solve the difference equation yK+4+4yK+3+8yK+2+8yK+1+4yK=0.
Solution: The characteristics equation is s4+4s3+8s2 (s2+2s+2)(s2+2s+2)=0
s = -1±i,-1±i
Therefore, the homogeneous solution of the equation is given by
yK=(C1+C2 K)(-1+i)K+(C3 +C4 K)(-1-i)K
Example 4
• Solve the difference equation ar-3ar-1+2ar-2=0.
• Solution: The characteristics equation is given by
• s2-3s+2=0 or (s-1)(s-2)=0
• ⇒ s = 1, 2
• Therefore, the homogeneous solution of the equation is given by
• ar=C1r+C2.2r.
Cases for finding the particular solution
• Case1: When R (n) is some constant A.
• We know that, the operation of E on any constant will be equal to the constant itself i.e.,
• EA=A
• Therefore, P (E) A = (C0 Er+C1 Er-1+C2 Er-2+⋯+Cn)A
• = (C0+C1+C2+⋯+Cn)A
• = P (1) A
• Particular Solution
• Therefore, using equation (ii), the particular solution of (i) is
• yn=Particular Solution,P(1)≠0
• P (1) is obtained by putting E = 1 in P (E).
Case2: When R (n) is of the form A. Zn, where A and Z are constants
We have, P (E) (A. Zn)={C0 Er+C1 Er-1+⋯+ Cn} (A.Zn)
=A{C0 Zr+n+C1 Zr+n-1+⋯+Cn Zn}
= A{C0 Zr+C1 Zr-1+⋯+Cn }. Zn
=AP(Z).Zn
To get, P (Z) put E=Z in P (E)
Therefore, Particular Solution, provided P (Z) ≠ 0
Thus, yn=Particular Solution, P (Z) ≠ 0
If A = 1, then yn=Particular Solution
When P (Z) = 0 then for equation
(i) (E-Z) yn= A. Zn
For this, the particular solution becomes A. Particular Solution Zn=A. n Zn-1
(ii) (E-Z)2 yn= A. Zn
For this, the particular solution becomes Particular Solution
(iii) (E-Z)3 yn= A. Zn
For this, the particular solution becomesParticular Solution and so on.
Case3: When R (n) be a polynomial of degree m is n.
We know that E≅1+∆
So, P (E) =P (1+∆)
Particular Solution
Which can be expanded in ascending power of ∆ as far as upto ∆m
⇒ Particular Solution =(b0+b1 ∆+b2 ∆+⋯.+bm ∆m+⋯)
⇒ Particular Solution.R(n)=( b0+b1 ∆+b2 ∆+⋯.+bm ∆m+⋯).R(n)
= b0 R(n)+b1 ∆ R(n)+⋯+bm ∆m R(n)
All other higher terms will be zero because R (n) is a polynomial of degree m.
Thus, the particular solution of equation (i), in this case will be
yn=b0 R(n)+b1 ∆ R(n)+⋯.+bm ∆m R(n).
Case4: When R (n) is of the form R(n).Zn,where R(n) is a polynomial of degree m and Z
is some constant
We have Er[Zn R(n)]=Zr+n R (n+r)=Zr.Zn.Er.R(n)=Zn (ZE)rR(n)
Similarly, we have
Particular Solution [Zn R(n)]=Zn Particular Solution .(R(n))= Zn [P(Z+Z∆)]-1.R(n)
Thus, the particular solution of equation (i), in this case will be
yn=Zn [P(Z+Z∆)]-1.R(n)
Example 1
• Find the particular solution of the difference equation
• 2ar+1-ar=12.
• Solution: The above equation can be written as
• (2E-1) ar=12
• The particular solution is given by
• ar=Particular Solution.12
• Put E=1, in the equation. The particular solution is ar=12
Example 2
• Find the particular solution of the difference equation ar-4ar-1+4ar-2=2r.
• Solution: The above equation can be written as
• (E2-4E+4) ar=2r
• Therefore, P (E) = E2-4E+4 = (E-2)2
• Thus, the particular solution is given by
• Particular Solution
Total solution
• The total solution or the general solution of a non-homogeneous linear
difference equation with constant coefficients is the sum of the
homogeneous solution and a particular solution. If no initial conditions are
given, obtain n linear equations in n unknowns and solve them, if possible
to get total solutions.
• If y(h) denotes the homogeneous solution of the recurrence relation and
y(p) indicates the particular solution of the recurrence relation then, the
total solution or the general solution y of the recurrence relation is given by
• y =y(h)+y(p).
example
• Solve the difference equation
• ar-4ar-1+4ar-2=3r+2r...........equation (i)
• Solution: The homogeneous solution of this equation is obtained by putting R.H.S equal to zero i.e.,
• ar-4ar-1+4ar-2=0
• Play Video
• The homogeneous solution is ar(h)= (C1+C2 r).2r
• The equation (i) can be written as (E2-4E+4) ar=3r+2r
• The particular solution is given as
• Total Solution
references
• Javapoint
• Tutorial point
• Brainly
• Doubtnut
• Byjus
• geeksforgeeks
Submitted to-
subiya zaidi
thankyou
