Level 8: Recursion and induction

Patterns and sequences · level 8 of 8 · rough age 17 and beyond (a guide for parents; anyone can start anywhere)

In level 7 you found formulas for sums and sequences and checked them on many cases. In this level you prove them for every whole number at once, with proof by induction, and learn its stronger form. Then you solve recurrences exactly, deriving Binet's formula for the Fibonacci numbers, and watch what happens when a function is applied again and again. The topic ends at the edge of what is known: a pattern so simple a child can follow it, which nobody has ever proved.

Lesson	You will be able to
Proof by induction	Explain why induction is a valid proof, and write induction proofs for sums such as \(1 + 3 + \cdots + (2n - 1) = n^2\) and the sum of the first \(n\) cubes
More induction	Prove divisibility facts and inequalities by induction, choose the right base case, and find the flaw in the "all horses are the same colour" proof
Strong induction	Use strong induction with enough base cases, to prove that every number from 2 up is a product of primes and that \(F_n < 2^n\)
Solving recurrences	Solve rules like \(a_n = 5a_{n-1} - 6a_{n-2}\) with the characteristic equation, and derive Binet's formula
Iteration and fixed points	Draw cobweb diagrams, find fixed points, and use the slope to tell when an iteration settles, runs away or cycles
Unsolved patterns	Explore the Collatz \(3n + 1\) problem, explain why huge computer checks are not a proof, and recognise patterns that broke

Previous: Level 7: series and sigma · This is the last level · Patterns topic page