Unit8
Recurrence Relations
The process for recursively finding the terms of a sequence is called the recurrence relation.
8.1.1 Definition:
A recurrence relationship is an equation that represents a series recursively where a function of the previous terms is the next term (Expressing Fn as some combination of Fi with i<n).
Example − Fibonacci series − Fn=Fn−1+Fn−2 Tower of Hanoi − Fn=2Fn−1+1 
A degree k or order k linear recurrence equation is a recurrence equation that is in the format of
on a sequence of numbers as a firstdegree polynomial.
Examples:
A linear homogeneous recurrence relation of the secondorder with. A recurrence relationship of the form is the constant coefficients.
ak = Aak−1 + Bak−2 for all integers k greater than some fixed integer, where A and B are fixed real numbers with B ≠ 0. Following given are examples of linear secondorder Homogeneous relationship of recurrence with constant coefficients: A) ak=3ak1 + 2ak+2 ; A=3 & B=2 B) ek=2ek2 ; A=0 & B=2 C) gk=gk1 + gk2 ; A=1 & B=1 
A relationship of recurrence is considered nonhomogeneous if it is in the form of Its associated homogeneous recurrence relation is Its associated homogeneous recurrence relation is The solution (an)of a nonhomogeneous recurrence relation has two parts. First part is the solution (ah)of the associated homogeneous recurrence relation and the second part is the particular solution (at).
The solution (an)of a nonhomogeneous recurrence relation has two parts. First part is the solution (ah)of the associated homogeneous recurrence relation and the second part is the particular solution (at). The first element of the approach is carried out using the protocols described in the previous section.
We find an effective research solution to find the exact solution. Let be the characteristic equation of the associated homogeneous recurrence relation and let x1 and x2 be its roots.

Generating functions are sequences in which each sequence term is expressed in a formal power series as a coefficient of a variable x.
Mathematically, the generating function would be − for an infinite number, say a0,a1,a2,...,ak,...
Some Domain Fields
For the following reasons, generating functions may be used −
 For solving a number of problems with counting. For instance, the number of ways to modify a note of Rs. 100 with denominations of Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 and Rs.50 notes
 To solve relationships with recurrence
 Any of the combinatorial identities to prove
 For the finding of asymptotic formulas for sequence words
References
1. D.S. Chandrasekharaiah: Graph Theory and Combinatorics, Prism,2005.
2. Chartrand Zhang: Introduction to Graph Theory, TMH, 2006.
3. Richard A. Brualdi: Introductory Combinatorics, 4th Edition, Pearson Education, 2004.
4. Geir Agnarsson & Raymond Geenlaw: Graph Theory, Pearson Education, 2007.