Proof by induction: sequences

Structure

To prove u_n = g(n):

• Basis: the given u_1 equals g(1).
• Assume u_k = g(k).
• Step: u_(k+1) = (recurrence applied to u_k) = (recurrence applied to g(k)); simplify to g(k + 1).
• Conclusion.

Example

u_(n+1) = 3u_n + 4, u_1 = 1. Prove u_n = 3ⁿ - 2.

n = 1: 3¹ - 2 = 1 = u_1. True.

Assume u_k = 3^k - 2. Then u_(k+1) = 3(3^k - 2) + 4 = 3^k+1 - 6 + 4 = 3^k+1 - 2, the formula with n = k + 1.

Conclusion.

Tips

Write out the first few terms to check the formula before you start. Always substitute the assumption into the recurrence: that is where the assumption is used, and you must show it.

Worked example

u_1 = 5 and u_(n+1) = 2u_n - 1. Prove by induction that u_n = 2ⁿ⁺¹ + 1.

1. n = 1: 2² + 1 = 5 = u_1. True.
2. Assume u_k = 2^k+1 + 1.
3. u_(k+1) = 2(2^k+1 + 1) - 1 = 2^k+2 + 2 - 1 = 2^k+2 + 1.
4. This is the formula with n = k + 1, so by induction it is true for all positive integers n.

Answer: Proved

Check yourself

1. u_1 = 1 and u_(n+1) = 3u_n + 4. Find u_4.
   Show answer

   79. u_2 = 7, u_3 = 25, u_4 = 79.

2. Check that u_n = 3ⁿ - 2 gives the same u_4.
   Show answer

   79. 3⁴ - 2 = 81 - 2 = 79.

3. u_1 = 5 and u_(n+1) = 2u_n - 1. Find u_3.
   Show answer

   17. u_2 = 9 and u_3 = 17.

4. Where is the assumption u_k = 3^k - 2 used in the inductive step?
   • It is substituted into u_(k+1) = 3u_k + 4
   • It is substituted into u_1
   • It is used only in the conclusion
   • It is not needed
   Show answer

   It is substituted into u_(k+1) = 3u_k + 4. u_(k+1) = 3u_k + 4 = 3(3^k - 2) + 4.

5. Which simplification is correct?
   • 3(3^k - 2) + 4 = 9^k - 2
   • 3(3^k - 2) + 4 = 3^k+1 + 2
   • 3(3^k - 2) + 4 = 3^k+1 - 2
   • 3(3^k - 2) + 4 = 3^k - 2
   Show answer

   3(3^k - 2) + 4 = 3^k+1 - 2. 3 × 3^k = 3^k+1, and -6 + 4 = -2.

6. u_1 = 2 and u_(n+1) = u_n + 2n + 1. Induction shows u_n = n² + c. Find c.
   Show answer

   1. u_1 = 2 gives 1 + c = 2, so c = 1. Step: (k² + 1) + 2k + 1 = (k + 1)² + 1.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Level in Mathematics, Further Mathematics and Pure Mathematics specification (issue 3), Unit FP1
• Pearson Edexcel IAL Further Pure Mathematics 1 scheme of work

Last updated 8 November 2026. Spotted a mistake? Tell us.