Try the code and the simulations beside the lesson.
What you will be able to do
write the characteristic equation of a linear recurrence;
solve it when the roots are different and when a root is repeated;
handle a constant term, and prove Binet's formula for the Fibonacci numbers.
Guessing a power
A table gives terms one by one. A formula gives the 100th term at once. For the recurrence
an=pan−1+qan−2
with numbers p and q, we try a power, an=xn with x=0. Then xn=pxn−1+qxn−2. Divide by xn−2:
x2=px+q.
This is the characteristic equation of the recurrence. Each root x gives a solution an=xn. The recurrence is called linear and homogeneous: each term is a fixed combination of earlier terms, with no extra constant.
Two different roots
If r and s are both solutions, so is Arn+Bsn for any numbers A and B. Check it: the recurrence adds and scales solutions.
Theorem. If the characteristic equation has two different roots r and s, every solution has the form an=Arn+Bsn.
Why every solution. Two starting values a0 and a1 fix the whole sequence. The equations A+B=a0 and Ar+Bs=a1 can always be solved for A and B, because r=s. So the formula matches the start, and then it matches every term.
Example. Solve an=3an−1+4an−2 with a0=0 and a1=5.
Characteristic equation.x2=3x+4, so (x−4)(x+1)=0 and the roots are 4 and −1.
General form.an=A⋅4n+B⋅(−1)n.
Starting values.A+B=0 and 4A−B=5, so A=1 and B=−1.
Answer.an=4n−(−1)n. Check: a2=16−1=15, and the recurrence gives 3×5+4×0=15.
A repeated root
If the characteristic equation is (x−r)2=0, the recurrence is an=2ran−1−r2an−2. The power rn is one solution. A second one is nrn. Check it:
2r(n−1)rn−1−r2(n−2)rn−2=(2n−2−n+2)rn=nrn.
So every solution has the form an=(A+Bn)rn.
Example.an=4an−1−4an−2 with a0=1 and a1=4. The equation x2−4x+4=0 has the double root 2. From A=1 and 2(A+B)=4 we get B=1, so an=(n+1)2n. The first terms are 1,4,12,32,80.
A constant term
A recurrence such as an=can−1+d, with c=1, has a fixed pointL, the number with L=cL+d. Subtract the two equations:
an−L=c(an−1−L).
So an−L=cn(a0−L). For an=2an−1+3 with a0=1, the fixed point is L=−3, and an+3=4×2n. So an=2n+2−3, which gives 1,5,13,29,61.
The same trick works for a second-order recurrence with a constant: find a constant solution L first, then solve for an−L.
Binet's formula
The Fibonacci recurrence Fn=Fn−1+Fn−2 has the equation x2=x+1, with roots
φ=21+5≈1.618,ψ=21−5≈−0.618.
The Greek letter φ (phi) is the golden ratio. From F0=0 and F1=1 we find A=51 and B=−51, so
Fn=5φn−ψn.
Since ∣ψ∣<1, the term 5ψn is tiny. So Fn is the whole number nearest to 5φn, and FnFn+1 tends to φ. The Lucas numbersLn=φn+ψn follow the same recurrence with L0=2 and L1=1, so they are whole numbers too.
Practise with new numbers
Try it in Python
The program solves a recurrence with sympy: it finds the roots of the characteristic equation, fits A and B, and compares the formula with the terms worked out one by one.
Common mistakes
Wrong signs in the equation. For an=pan−1+qan−2 the equation is x2−px−q=0.
Using Arn+Bsn with a double root. With r=s you need (A+Bn)rn.
Fitting with the wrong start. If the sequence starts at a1, use n=1 and n=2 to fit A and B.
Forgetting the fixed point.an=can−1+d is not solved by Acn alone.
Remember these
an=pan−1+qan−2 has the characteristic equation x2=px+q.
Different roots: an=Arn+Bsn. A double root: an=(A+Bn)rn.
A constant term: work with an−L, where L is the fixed point.
Fn=5φn−ψn, and Fn is the whole number nearest to 5φn.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Write the characteristic equation of an=7an−1−12an−2 and find its roots.
Solve an=an−1+2an−2 with a0=2 and a1=1.
Solve an=6an−1−9an−2 with a0=2 and a1=3.
Solve an=3an−1−2 with a0=4.
Use Binet's formula to explain why Fn is always a whole number, even though it is written with 5.
References
R. A. Brualdi, Introductory Combinatorics, Chapter 7, linear homogeneous recurrence relations.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Chapter 6, Fibonacci numbers.
Enroll free in Recurrences and Counting by Recursion
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.