HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Strong Induction, Inequalities and Recursion
  1. 1Inequalities by induction
  2. 2Strong induction and the well-ordering principle
  3. 3Sequences defined by recursion
  1. Mathematics
  2. /Strong Induction, Inequalities and Recursion
  3. /Sequences defined by recursion

Course 26.2·Lesson 3 of 3

Sequences defined by recursion

A recursion gives each term from earlier terms, such as an+1=2an+1a_{n + 1} = 2a_n + 1an+1​=2an​+1

Lesson 3 of 3Show all lessonsHide
Strong Induction, Inequalities and Recursion
  1. 1Inequalities by induction
  2. 2Strong induction and the well-ordering principle
  3. 3Sequences defined by recursion

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.\displaystyle a_1 = 1, \qquad a_{n + 1} = 2a_n + 1.a1​=1,an+1​=2an​+1.

The terms are 1,3,7,15,31,…1, 3, 7, 15, 31, \dots1,3,7,15,31,…. Each is one less than a power of 222, so we guess an=2n−1a_n = 2^n - 1an​=2n−1. Induction proves it.

  1. Base case. a1=1=21−1a_1 = 1 = 2^1 - 1a1​=1=21−1.
  2. Step. Assume ak=2k−1a_k = 2^k - 1ak​=2k−1. Then ak+1=2(2k−1)+1=2k+1−1a_{k + 1} = 2(2^k - 1) + 1 = 2^{k + 1} - 1ak+1​=2(2k−1)+1=2k+1−1.

The same method works for every rule an+1=ran+ca_{n + 1} = ra_n + can+1​=ran​+c with r≠1r \ne 1r=1. Write L=cr−1L = \dfrac{c}{r - 1}L=r−1c​. Then an+La_n + Lan​+L is multiplied by rrr at each step, so

an=rn−1(a1+L)−L.\displaystyle a_n = r^{n - 1}(a_1 + L) - L.an​=rn−1(a1​+L)−L.

The Fibonacci numbers

The Fibonacci numbers are F1=1F_1 = 1F1​=1, F2=1F_2 = 1F2​=1 and Fn+1=Fn+Fn−1F_{n + 1} = F_n + F_{n - 1}Fn+1​=Fn​+Fn−1​. They run 1,1,2,3,5,8,13,21,…1, 1, 2, 3, 5, 8, 13, 21, \dots1,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−1F_1 + F_2 + \dots + F_n = F_{n + 2} - 1F1​+F2​+⋯+Fn​=Fn+2​−1.

  1. Base case. F1=1=F3−1=2−1F_1 = 1 = F_3 - 1 = 2 - 1F1​=1=F3​−1=2−1.
  2. Step. Assume the sum up to kkk is Fk+2−1F_{k + 2} - 1Fk+2​−1. Add Fk+1F_{k + 1}Fk+1​: the result is Fk+2+Fk+1−1=Fk+3−1F_{k + 2} + F_{k + 1} - 1 = F_{k + 3} - 1Fk+2​+Fk+1​−1=Fk+3​−1.

This one needs only ordinary induction, because the sum looks back one place.

A bound. Fn<2nF_n < 2^nFn​<2n for every n≥1n \ge 1n≥1.

  1. Base cases. F1=1<2F_1 = 1 < 2F1​=1<2 and F2=1<4F_2 = 1 < 4F2​=1<4.
  2. Step. Let k+1≥3k + 1 \ge 3k+1≥3 and assume the bound for all smaller indices. Then Fk+1=Fk+Fk−1<2k+2k−1<2k+2k=2k+1F_{k + 1} = F_k + F_{k - 1} < 2^k + 2^{k - 1} < 2^k + 2^k = 2^{k + 1}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)nF_{n + 1}F_{n - 1} - F_n^2 = (-1)^nFn+1​Fn−1​−Fn2​=(−1)n for every n≥2n \ge 2n≥2. At n=2n = 2n=2: 2×1−1=1=(−1)22 \times 1 - 1 = 1 = (-1)^22×1−1=1=(−1)2. For the step, replace Fk+2F_{k + 2}Fk+2​ by Fk+1+FkF_{k + 1} + F_kFk+1​+Fk​:

Fk+2Fk−Fk+12=Fk2+Fk+1Fk−Fk+12=Fk2−Fk+1(Fk+1−Fk)=Fk2−Fk+1Fk−1.\displaystyle F_{k + 2}F_k - F_{k + 1}^2 = F_k^2 + F_{k + 1}F_k - F_{k + 1}^2 = F_k^2 - F_{k + 1}(F_{k + 1} - F_k) = F_k^2 - F_{k + 1}F_{k - 1}.Fk+2​Fk​−Fk+12​=Fk2​+Fk+1​Fk​−Fk+12​=Fk2​−Fk+1​(Fk+1​−Fk​)=Fk2​−Fk+1​Fk−1​.

That is −(−1)k=(−1)k+1-(-1)^k = (-1)^{k + 1}−(−1)k=(−1)k+1.

Two terms back: the characteristic equation

A rule such as an=5an−1−6an−2a_n = 5a_{n - 1} - 6a_{n - 2}an​=5an−1​−6an−2​ is solved by trying an=xna_n = x^nan​=xn. This gives x2=5x−6x^2 = 5x - 6x2=5x−6, with roots 222 and 333. So an=A×2n+B×3na_n = A \times 2^n + B \times 3^nan​=A×2n+B×3n, and the first two terms fix AAA and BBB. A short strong induction then proves the formula. A later chapter on recurrences treats this in full.

Increasing and bounded

Let a1=1a_1 = 1a1​=1 and an+1=2+ana_{n + 1} = \sqrt{2 + a_n}an+1​=2+an​​. The terms are 111, 3≈1.732\sqrt{3} \approx 1.7323​≈1.732, about 1.9321.9321.932, and so on. Two facts can be proved by induction.

  1. Bounded: an<2a_n < 2an​<2. True for n=1n = 1n=1. If ak<2a_k < 2ak​<2, then ak+1=2+ak<4=2a_{k + 1} = \sqrt{2 + a_k} < \sqrt{4} = 2ak+1​=2+ak​​<4​=2.
  2. Increasing: an+1>ana_{n + 1} > a_nan+1​>an​. For 0<a<20 < a < 20<a<2 we have 2+a−a2=(2−a)(1+a)>02 + a - a^2 = (2 - a)(1 + a) > 02+a−a2=(2−a)(1+a)>0, so 2+a>a\sqrt{2 + a} > a2+a​>a.

A sequence that rises and stays below a fixed number settles on a limit. If the limit is LLL, then L=2+LL = \sqrt{2 + L}L=2+L​, which gives L=2L = 2L=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−12^n - 12n−1, two Fibonacci identities and the rising sequence 2+an\sqrt{2 + a_n}2+an​​.

Read it first. Then run it. Do the Cassini values alternate between 111 and −1-1−1?

1. Change the first rule to a = 3 * a + 2 and the formula to 2 * 3 ** (n - 1) - 1. Do the columns still agree?

2. Change math.sqrt(2 + a) to math.sqrt(12 + a). Which number does the sequence approach now?

Common mistakes

  • One base case for a two-step rule. The Fibonacci rule needs F1F_1F1​ and F2F_2F2​.
  • Guessing without proving. A guess from five terms is only a guess.
  • Squaring an inequality carelessly. a<2a < 2a<2 gives 2+a<2\sqrt{2 + a} < 22+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+ca_{n + 1} = ra_n + can+1​=ran​+c gives an=rn−1(a1+L)−La_n = r^{n - 1}(a_1 + L) - Lan​=rn−1(a1​+L)−L with L=cr−1L = \dfrac{c}{r - 1}L=r−1c​.
  • F1+⋯+Fn=Fn+2−1F_1 + \dots + F_n = F_{n + 2} - 1F1​+⋯+Fn​=Fn+2​−1, Fn<2nF_n < 2^nFn​<2n, and Fn+1Fn−1−Fn2=(−1)nF_{n + 1}F_{n - 1} - F_n^2 = (-1)^nFn+1​Fn−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.

  1. A sequence has a1=2a_1 = 2a1​=2 and an+1=3ana_{n + 1} = 3a_nan+1​=3an​. Guess a formula and prove the step.
  1. Use the formula with LLL to find ana_nan​ for a1=3a_1 = 3a1​=3 and an+1=2an−1a_{n + 1} = 2a_n - 1an+1​=2an​−1.
  1. Check Cassini's identity for n=6n = 6n=6.
  1. Why does the bound Fn<2nF_n < 2^nFn​<2n need two base cases?
  1. For a1=1a_1 = 1a1​=1 and an+1=6+ana_{n + 1} = \sqrt{6 + a_n}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.
No payment. You can leave at any time.

Problems (3)

A bacteria count in a culture follows a simple model…Hard · High School (11–12) · by StemPy Lab
Squares with sides 1, 1, 2, 3, 5, 8, … (the Fibonacci numbers F₁, F₂, …) are placed one after…Advanced · High School (11–12) · by StemPy Lab
A sequence is defined by a₁ = 1 and a_(n + 1) = √(6 + an)…Advanced · High School (11–12) · by StemPy Lab
That was the last lessonBack to the course: take the test
← Strong Induction, Inequalities and Recursion
← Strong induction and the well-ordering principleNext →

Discussion (0)

Log in to join the discussion.

Loading…

or the Fibonacci rule
Fn+1=Fn+Fn−1F_{n + 1} = F_n + F_{n - 1}Fn+1​=Fn​+Fn−1​
. 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+ana_{n + 1} = \sqrt{2 + a_n}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.

Python Labs (1)

Fibonacci identities by computerPython Lab · by StemPy Lab

Question Sets (1)

Strong Induction, Inequalities and Recursion: Concept Check10 questions · by StemPy Lab

Notes (1)

Strong Induction, Inequalities and Recursion: Quick RevisionNote · by StemPy Lab