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
Recurrences and Counting by Recursion
  1. 1Setting up a recurrence
  2. 2Solving linear recurrences
  3. 3Derangements and Catalan numbers
  1. Mathematics
  2. /Recurrences and Counting by Recursion
  3. /Solving linear recurrences

Course 30.2·Lesson 2 of 3

Solving linear recurrences

A linear recurrence an=pan−1+qan−2a_n = pa_{n-1} + qa_{n-2}an​=pan−1​+qan−2​

Lesson 2 of 3Show all lessonsHide
Recurrences and Counting by Recursion
  1. 1Setting up a recurrence
  2. 2Solving linear recurrences
  3. 3Derangements and Catalan numbers

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 100100100th term at once. For the recurrence

an=pan−1+qan−2\displaystyle a_n = pa_{n-1} + qa_{n-2}an​=pan−1​+qan−2​

with numbers ppp and qqq, we try a power, an=xna_n = x^nan​=xn with x≠0x \ne 0x=0. Then xn=pxn−1+qxn−2x^n = px^{n-1} + qx^{n-2}xn=pxn−1+qxn−2. Divide by xn−2x^{n-2}xn−2:

x2=px+q.\displaystyle x^2 = px + q.x2=px+q.

This is the characteristic equation of the recurrence. Each root xxx gives a solution an=xna_n = x^nan​=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 rrr and sss are both solutions, so is Arn+BsnAr^n + Bs^nArn+Bsn for any numbers AAA and BBB. Check it: the recurrence adds and scales solutions.

Theorem. If the characteristic equation has two different roots rrr and sss, every solution has the form an=Arn+Bsna_n = Ar^n + Bs^nan​=Arn+Bsn.

Why every solution. Two starting values a0a_0a0​ and a1a_1a1​ fix the whole sequence. The equations A+B=a0A + B = a_0A+B=a0​ and Ar+Bs=a1Ar + Bs = a_1Ar+Bs=a1​ can always be solved for AAA and BBB, because r≠sr \ne sr=s. So the formula matches the start, and then it matches every term.

Example. Solve an=3an−1+4an−2a_n = 3a_{n-1} + 4a_{n-2}an​=3an−1​+4an−2​ with a0=0a_0 = 0a0​=0 and a1=5a_1 = 5a1​=5.

  1. Characteristic equation. x2=3x+4x^2 = 3x + 4x2=3x+4, so (x−4)(x+1)=0(x - 4)(x + 1) = 0(x−4)(x+1)=0 and the roots are 444 and −1-1−1.
  2. General form. an=A⋅4n+B⋅(−1)na_n = A \cdot 4^n + B \cdot (-1)^nan​=A⋅4n+B⋅(−1)n.
  3. Starting values. A+B=0A + B = 0A+B=0 and 4A−B=54A - B = 54A−B=5, so A=1A = 1A=1 and B=−1B = -1B=−1.
  4. Answer. an=4n−(−1)na_n = 4^n - (-1)^nan​=4n−(−1)n. Check: a2=16−1=15a_2 = 16 - 1 = 15a2​=16−1=15, and the recurrence gives 3×5+4×0=153 \times 5 + 4 \times 0 = 153×5+4×0=15.

A repeated root

If the characteristic equation is (x−r)2=0(x - r)^2 = 0(x−r)2=0, the recurrence is an=2ran−1−r2an−2a_n = 2ra_{n-1} - r^2a_{n-2}an​=2ran−1​−r2an−2​. The power rnr^nrn is one solution. A second one is nrnnr^nnrn. Check it:

2r(n−1)rn−1−r2(n−2)rn−2=(2n−2−n+2)rn=nrn.\displaystyle 2r(n - 1)r^{n-1} - r^2(n - 2)r^{n-2} = (2n - 2 - n + 2)r^n = nr^n.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)rna_n = (A + Bn)r^nan​=(A+Bn)rn.

Example. an=4an−1−4an−2a_n = 4a_{n-1} - 4a_{n-2}an​=4an−1​−4an−2​ with a0=1a_0 = 1a0​=1 and a1=4a_1 = 4a1​=4. The equation x2−4x+4=0x^2 - 4x + 4 = 0x2−4x+4=0 has the double root 222. From A=1A = 1A=1 and 2(A+B)=42(A + B) = 42(A+B)=4 we get B=1B = 1B=1, so an=(n+1)2na_n = (n + 1)2^nan​=(n+1)2n. The first terms are 1,4,12,32,801, 4, 12, 32, 801,4,12,32,80.

A constant term

A recurrence such as an=can−1+da_n = ca_{n-1} + dan​=can−1​+d, with c≠1c \ne 1c=1, has a fixed point LLL, the number with L=cL+dL = cL + dL=cL+d. Subtract the two equations:

an−L=c(an−1−L).\displaystyle a_n - L = c(a_{n-1} - L).an​−L=c(an−1​−L).

So an−L=cn(a0−L)a_n - L = c^n(a_0 - L)an​−L=cn(a0​−L). For an=2an−1+3a_n = 2a_{n-1} + 3an​=2an−1​+3 with a0=1a_0 = 1a0​=1, the fixed point is L=−3L = -3L=−3, and an+3=4×2na_n + 3 = 4 \times 2^nan​+3=4×2n. So an=2n+2−3a_n = 2^{n+2} - 3an​=2n+2−3, which gives 1,5,13,29,611, 5, 13, 29, 611,5,13,29,61.

The same trick works for a second-order recurrence with a constant: find a constant solution LLL first, then solve for an−La_n - Lan​−L.

Binet's formula

The Fibonacci recurrence Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}Fn​=Fn−1​+Fn−2​ has the equation x2=x+1x^2 = x + 1x2=x+1, with roots

φ=1+52≈1.618,ψ=1−52≈−0.618.\displaystyle \varphi = \dfrac{1 + \sqrt{5}}{2} \approx 1.618, \qquad \psi = \dfrac{1 - \sqrt{5}}{2} \approx -0.618.φ=21+5​​≈1.618,ψ=21−5​​≈−0.618.

The Greek letter φ\varphiφ (phi) is the golden ratio. From F0=0F_0 = 0F0​=0 and F1=1F_1 = 1F1​=1 we find A=15A = \dfrac{1}{\sqrt{5}}A=5​1​ and B=−15B = -\dfrac{1}{\sqrt{5}}B=−5​1​, so

Fn=φn−ψn5.\displaystyle F_n = \dfrac{\varphi^n - \psi^n}{\sqrt{5}}.Fn​=5​φn−ψn​.

Since ∣ψ∣<1|\psi| < 1∣ψ∣<1, the term ψn5\dfrac{\psi^n}{\sqrt{5}}5​ψn​ is tiny. So FnF_nFn​ is the whole number nearest to φn5\dfrac{\varphi^n}{\sqrt{5}}5​φn​, and Fn+1Fn\dfrac{F_{n+1}}{F_n}Fn​Fn+1​​ tends to φ\varphiφ. The Lucas numbers Ln=φn+ψnL_n = \varphi^n + \psi^nLn​=φn+ψn follow the same recurrence with L0=2L_0 = 2L0​=2 and L1=1L_1 = 1L1​=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 AAA and BBB, and compares the formula with the terms worked out one by one.

Read it first. Then run it. Do the two lists agree?

1. Change the recurrence to p, q = 4, -4 and the start to a0, a1 = 1, 4. What does sympy print for the roots, and why does the program stop?

2. Change it to p, q = 1, 1 with a0, a1 = 0, 1. Which famous formula do you get?

Common mistakes

  • Wrong signs in the equation. For an=pan−1+qan−2a_n = pa_{n-1} + qa_{n-2}an​=pan−1​+qan−2​ the equation is x2−px−q=0x^2 - px - q = 0x2−px−q=0.
  • Using Arn+BsnAr^n + Bs^nArn+Bsn with a double root. With r=sr = sr=s you need (A+Bn)rn(A + Bn)r^n(A+Bn)rn.
  • Fitting with the wrong start. If the sequence starts at a1a_1a1​, use n=1n = 1n=1 and n=2n = 2n=2 to fit AAA and BBB.
  • Forgetting the fixed point. an=can−1+da_n = ca_{n-1} + dan​=can−1​+d is not solved by AcnAc^nAcn alone.

Remember these

  • an=pan−1+qan−2a_n = pa_{n-1} + qa_{n-2}an​=pan−1​+qan−2​ has the characteristic equation x2=px+qx^2 = px + qx2=px+q.
  • Different roots: an=Arn+Bsna_n = Ar^n + Bs^nan​=Arn+Bsn. A double root: an=(A+Bn)rna_n = (A + Bn)r^nan​=(A+Bn)rn.
  • A constant term: work with an−La_n - Lan​−L, where LLL is the fixed point.
  • Fn=φn−ψn5F_n = \dfrac{\varphi^n - \psi^n}{\sqrt{5}}Fn​=5​φn−ψn​, and FnF_nFn​ is the whole number nearest to φn5\dfrac{\varphi^n}{\sqrt{5}}5​φn​.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. Write the characteristic equation of an=7an−1−12an−2a_n = 7a_{n-1} - 12a_{n-2}an​=7an−1​−12an−2​ and find its roots.
  1. Solve an=an−1+2an−2a_n = a_{n-1} + 2a_{n-2}an​=an−1​+2an−2​ with a0=2a_0 = 2a0​=2 and a1=1a_1 = 1a1​=1.
  1. Solve an=6an−1−9an−2a_n = 6a_{n-1} - 9a_{n-2}an​=6an−1​−9an−2​ with a0=2a_0 = 2a0​=2 and a1=3a_1 = 3a1​=3.
  1. Solve an=3an−1−2a_n = 3a_{n-1} - 2an​=3an−1​−2 with a0=4a_0 = 4a0​=4.
  1. Use Binet's formula to explain why FnF_nFn​ is always a whole number, even though it is written with 5\sqrt{5}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.
No payment. You can leave at any time.

Problems (4)

A sequence starts with a₀ = 2 and a₁ = 5, and every later term follows the rule an = 5a_(n-1)…Hard · High School (11–12) · by StemPy Lab
A sequence has a₀ = 1 and a₁ = 6, and an = 6a_(n-1) - 9a_(n-2) for n ≥ 2…Hard · High School (11–12) · by StemPy Lab
A culture of cells triples every hour. At the end of each hour a technician removes 4 thousand…Advanced · High School (11–12) · by StemPy Lab
Next: lesson 3Derangements and Catalan numbers
← Recurrences and Counting by Recursion
← Setting up a recurrenceDerangements and Catalan numbers →

Discussion (0)

Log in to join the discussion.

Loading…

is solved by trying
an=xna_n = x^nan​=xn
. This gives the characteristic equation
x2=px+qx^2 = px + qx2=px+q
. With two different roots
rrr
and
sss
,
an=Arn+Bsna_n = Ar^n + Bs^nan​=Arn+Bsn
; with one repeated root
rrr
,
an=(A+Bn)rna_n = (A + Bn)r^nan​=(A+Bn)rn
. The starting values fix
AAA
and
BBB
. A constant term is removed by moving to the fixed point first.
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.

The golden ratio is φ = (1 + √5)/2, and its partner is ψ = (1 - √5)/2…Advanced · High School (11–12) · by StemPy Lab