A recursion gives each term from earlier terms, such as an+1=2an+1
Lesson 3 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
find and prove a closed formula for a recursive sequence;
prove identities and bounds for the Fibonacci numbers;
show that a recursive sequence is increasing and bounded.
A rule that builds a sequence
A recursion gives the first term and a rule for the next term:
a1=1,an+1=2an+1.
The terms are 1,3,7,15,31,…. Each is one less than a power of 2, so we guess an=2n−1. Induction proves it.
Base case.a1=1=21−1.
Step. Assume ak=2k−1. Then ak+1=2(2k−1)+1=2k+1−1.
The same method works for every rule an+1=ran+c with r=1. Write L=r−1c. Then an+L is multiplied by r at each step, so
an=rn−1(a1+L)−L.
The Fibonacci numbers
The Fibonacci numbers are F1=1, F2=1 and Fn+1=Fn+Fn−1. They run 1,1,2,3,5,8,13,21,…. The rule looks back two places, so a proof often needs strong induction with two base cases.
A sum.F1+F2+⋯+Fn=Fn+2−1.
Base case.F1=1=F3−1=2−1.
Step. Assume the sum up to k is Fk+2−1. Add Fk+1: the result is Fk+2+Fk+1−1=Fk+3−1.
This one needs only ordinary induction, because the sum looks back one place.
A bound.Fn<2n for every n≥1.
Base cases.F1=1<2 and F2=1<4.
Step. Let k+1≥3 and assume the bound for all smaller indices. Then Fk+1=Fk+Fk−1<2k+2k−1<2k+2k=2k+1.
The step used two earlier terms, so we needed two base cases.
Cassini's identity.Fn+1Fn−1−Fn2=(−1)n for every n≥2. At n=2: 2×1−1=1=(−1)2. For the step, replace Fk+2 by Fk+1+Fk:
A rule such as an=5an−1−6an−2 is solved by trying an=xn. This gives x2=5x−6, with roots 2 and 3. So an=A×2n+B×3n, and the first two terms fix A and B. A short strong induction then proves the formula. A later chapter on recurrences treats this in full.
Increasing and bounded
Let a1=1 and an+1=2+an. The terms are 1, 3≈1.732, about 1.932, and so on. Two facts can be proved by induction.
Bounded: an<2. True for n=1. If ak<2, then ak+1=2+ak<4=2.
Increasing: an+1>an. For 0<a<2 we have 2+a−a2=(2−a)(1+a)>0, so 2+a>a.
A sequence that rises and stays below a fixed number settles on a limit. If the limit is L, then L=2+L, which gives L=2. This is the style of many ISI and olympiad questions. The limit itself is a topic of calculus.
A graph of the curve y = square root of (2 + x) in blue and the line y = x in grey, for x from 0 to 2.5. They meet at the point (2, 2). A red staircase starts at x = 1 on the line, goes up to the curve, across to the line, up to the curve again, and so on, with steps that get smaller and smaller as they close in on the point (2, 2). The terms a1 = 1, a2 = 1.732 and a3 = 1.932 are marked on the x axis.
Practise with new numbers
Try it in Python
The program checks the formula 2n−1, two Fibonacci identities and the rising sequence 2+an.
Common mistakes
One base case for a two-step rule. The Fibonacci rule needs F1 and F2.
Guessing without proving. A guess from five terms is only a guess.
Squaring an inequality carelessly.a<2 gives 2+a<2 because the square root increases.
Assuming a limit exists. First show the sequence is increasing and bounded.
Remember these
List terms, guess, prove.
an+1=ran+c gives an=rn−1(a1+L)−L with L=r−1c.
F1+⋯+Fn=Fn+2−1, Fn<2n, and Fn+1Fn−1−Fn2=(−1)n.
Increasing and bounded: prove each by induction.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
A sequence has a1=2 and an+1=3an. Guess a formula and prove the step.
Use the formula with L to find an for a1=3 and an+1=2an−1.
Check Cassini's identity for n=6.
Why does the bound Fn<2n need two base cases?
For a1=1 and an+1=6+an, which number is a bound, and what is the limit?
References
Arthur Engel, Problem-Solving Strategies, Chapter 8, The Induction Principle, and Chapter 9, Sequences.
Richard Hammack, Book of Proof, third edition, Chapter 10, the section on Fibonacci numbers.
Enroll free in Strong Induction, Inequalities and 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.
. Induction is the natural proof for such sequences: list a few terms, guess a closed formula and prove it. Strong induction proves Fibonacci identities and bounds, and induction also shows that a sequence such as
an+1=2+an
is increasing and bounded.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself
This lesson is free to read. Enroll free to keep your place and take the tests.