Induction, Recursion and Recurrence Relations

A loop and a recursive function both compute by repeating. Induction proves that such repeated processes are correct; recurrence relations describe how their cost grows.

This unit gives you the tools to prove statements for all integers and to solve the recurrences that arise from algorithms.

4.1 Mathematical induction

To prove P (n) for all integers n \geq n_{0}:

1. Base case: prove P (n_{0}).
2. Inductive step: assume P (k) (the inductive hypothesis) for an arbitrary k \geq n_{0} and prove P (k + 1).

Then P (n) holds for all n \geq n_{0}, like dominoes: the first falls, and each one knocks over the next.

Strong induction. Assume P (j) for all j with n_{0} \leq j \leq k, and prove P (k + 1).

Example every integer n \geq 2 is a product of primes.

If n is prime, done; otherwise n = a b with 2 \leq a ,\ b < n, and by hypothesis each is a product of primes, so n is too. ∎ Another: any postage of 12 cents or more can be made with 4-cent and 5-cent stamps (base cases 12, 13, 14, 15; for k + 1 \geq 16 use k - 3, add one 4-cent stamp).

Common mistakes: forgetting the base case; assuming what must be proved; using a step that only works for some k; "proving" false statements (all horses are the same colour fails at k = 1 \to 2).

Induction: knock over the first domino, then prove each one knocks the next

Mathematical induction is the domino argument written as a proof. The base case says the first domino falls. The inductive step says: if domino k falls, then domino k + 1 falls. Together they make every domino fall.

Plate 4.1 uses the claim "the sum of the first n odd numbers is n squared": the table checks it for the first eight values, and the step k^{2} + (2 k + 1) = (k + 1)^{2} is checked for k = 1 to 50, though the algebra proves it for every k.

(a) Dominoes: if one falls, the next one falls

(b) Sum of the first n odd numbers is n squared

4.2 Recursive definitions

A recursive definition has a base and a recursive rule.

• Factorial: 0 ! = 1 ,\ (n + 1) ! = ( n + 1)·n!.
• Fibonacci: F_{0} = 0 ,\ F_{1} = 1 ,\ F_{n} = F_{n-1} + F_{n-2} \to 0 ,\ 1 ,\ 1 ,\ 2 ,\ 3 ,\ 5 ,\ 8 ,\ 13 ,\ 21 ,\ \ldots
• Sets: the set of strings over {0, 1} with no "00"; well-formed formulas; binary trees (a tree is empty or a root with two subtrees).

Structural induction proves properties of recursively defined objects: show the base objects have it, and that each construction rule preserves it.

Example a full binary tree with i internal nodes has i + 1 leaves (base: a single leaf has 0 internal and 1 leaf; joining two trees with i_{1} ,\ i_{2} internal nodes under a new root gives i_{1} + i_{2} + 1 internal and (i_{1} + 1) + (i_{2} + 1) = i + 1 leaves).

Recursion in code. Every recursive function has a base case and a step that moves toward it:

long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
int fib(int n)   { return n < 2 ? n : fib(n - 1) + fib(n - 2); } /* exponential time */

The inductive proof that fact(n) returns n ! mirrors the code. The naïve fib takes about \varphi^{n} calls (\varphi \approx 1.618); memoisation reduces it to linear.

4.3 Linear recurrence relations

A recurrence relation gives a_{n} in terms of earlier terms. A linear homogeneous recurrence of order k with constant coefficients: a_{n} = c_{1} a_{n-1} + \ldots + c_{k} a_{n-k}.

Method. Try a_{n} = r^{n}: the characteristic equation r^{k} = c_{1} r^{k-1} + \ldots + c_{k}.

Roots	General solution (order 2)
distinct r_{1} \neq r_{2}	a_{n} = A r_{1}^{n} + B r_{2}^{n}
repeated r	a_{n} = ( A + Bn) r^{n}

Use the initial conditions to find A and B.

Non-homogeneous a_{n} = (homogeneous part) + f (n): the solution is a_{n} = (homogeneous solution) + (one particular solution). For constant f ,\ t r y a constant; for f (n) = n ,\ t r y p n + q.

Example a_{n} = 2 a_{n-1} + 1 ,\ a_{0} = 0: particular a_{n} = - 1 (since - 1 = - 2 + 1), homogeneous A \cdot 2^{n} ;\ a_{0} = A - 1 = 0 ⇒ a_{n} = 2^{n} - 1.

Modelling.

Tower of Hanoi moving n discs needs T_{n} = 2 T_{n-1} + 1 ,\ T_{1} = 1 ⇒ T_{n} = 2^{n} - 1: 10 discs take 1023 moves; 64 discs take about 1.8 \times 10^{19}.

Compound interest B_{n} = 1.05 B_{n-1} + 1000 ( a yearly deposit). Bit strings with no two consecutive 0s: s_{n} = s_{n-1} + s_{n-2} ,\ s_{1} = 2 ,\ s_{2} = 3 \to 2 ,\ 3 ,\ 5 ,\ 8 ,\ 13 ( a Fibonacci shift: s_{5} = 13).

Counting regions n lines in a plane (general position) give R_{n} = R_{n-1} + n ,\ R_{0} = 1 \Rightarrow R_{n} = 1 + \frac{n (n + 1)}{2}.

Fibonacci in a sunflower

The Fibonacci numbers come from the recurrence F (n + 1) = F (n) + F (n - 1).

The ratio of neighbours settles quickly at the golden ratio 1.618..., and a plant that places each new seed 137.5 degrees (the golden angle) round the previous one packs the seeds with no gaps and no straight rays.

Counting the spirals on a sunflower head usually gives two neighbouring Fibonacci numbers such as 34 and 55. Plate 4.2 computes the ratios for n = 1 to 12 and the golden angle.

(a) Sunflower head: seeds packed on Fibonacci spirals

(b) Ratio of neighbouring Fibonacci numbers

4.4 Divide-and-conquer recurrences

Algorithms that split a problem of size n into a subproblems of size \frac{n}{b} plus f (n) extra work satisfy T (n) = a T \left( \frac{n}{b} \right) + f (n).

Master theorem (for f (n) = \Theta (n^{d})): compare d with \log_{b} a.

Case	Condition	T (n)
1	d < \log_{b} a	\Theta (n^{\log_{b} a})
2	d = \log_{b} a	\Theta (n^{d} \log n)
3	d > \log_{b} a	\Theta (n^{d})

Algorithm	Recurrence	\log_{b} a v s d	Result
Binary search	T (n) = T \left( \frac{n}{2} \right) + 1	\log_{2} 1 = 0 = d	\Theta (\log n)
Merge sort	T (n) = 2 T \left( \frac{n}{2} \right) + n	1 = 1	\Theta (n \log n)
Sum or maximum of an array by halving	T (n) = 2 T \left( \frac{n}{2} \right) + 1	1 > 0	\Theta (n)
Karatsuba multiplication	T (n) = 3 T \left( \frac{n}{2} \right) + n	\log_{2} 3 \approx 1.585 > 1	\Theta (n^{1} . 585)
Strassen	T (n) = 7 T \left( \frac{n}{2} \right) + n^{2}	\log_{2} 7 \approx 2.807 > 2	\Theta (n^{2} . 807)
Naïve recursive Fibonacci	T (n) = T (n - 1) + T (n - 2) + 1	not of this form	\Theta (\varphi^{n})

4.5 The recursion tree of merge sort

A divide-and-conquer recurrence such as T (n) = 2 T \left( \frac{n}{2} \right) + n can be read from a picture (Figure 4.1).

Sorting 8 items splits them into two halves of 4, then four of 2, then eight of 1: that is 3 splits, so the tree has \log_{2} 8 + 1 = 4 levels.

At every level the merging work adds up to n = 8 (each item is touched once), so the total is n per level × (\log_{2} n + 1) levels, about n \log n.

The same drawing explains why merge sort beats bubble sort (n^{2}) for large n: for n = 1,000,000 it is roughly 20 million steps against a million million.

4.6 Eight uses of induction and recursion

1. Proving programs correct. A loop invariant is proved by induction on the number of iterations: true before the loop, preserved by each pass. This is how binary search and sorting routines are certified.
2. Recursive programs. Factorial, Fibonacci, tree traversal and directory walking are recursive definitions turned into code. Each has a base case and a step that moves toward it, exactly as an induction proof does.
3. Divide and conquer. Merge sort, quicksort and fast multiplication split a problem and combine the answers. Their running times are solved from recurrences like Figure 4.1.
4. Algorithm cost. The recurrence H (n) = 2 H (n - 1) + 1 of the Tower of Hanoi gives 2^{n} - 1 moves, so 10 disks need 1,023 moves and 64 disks are hopeless. Recurrences predict whether a method will finish in a lifetime.
5. Data structures. A binary tree, a linked list and a nested folder are recursive structures: each is either empty or a root with smaller copies. Their algorithms are naturally recursive.
6. Growth models. Compound interest on a deposit, population growth and loan balances satisfy a_{n} = r \cdot a_{n - 1} + d. Solving the recurrence gives a formula for any month. Banks in Nepal compute EMIs this way.
7. Dynamic programming. Shortest paths, edit distance and knapsack problems build the answer for size n from stored answers for smaller sizes. Spell-checkers and DNA matching use it.
8. Language and grammars. Programming-language syntax is defined recursively (an expression is a number or an expression plus an expression). Compilers parse by recursion and check properties by structural induction.

Formula and fact sheet

• Induction: base case + (P (k) \Rightarrow P (k + 1)). Strong induction assumes all earlier cases.
• \sum i = \frac{n (n + 1)}{2} ;\ \sum (2 i - 1) = n^{2} ;\ \sum r^{i} = \frac{r^{n+1} - 1}{r - 1}.
• Characteristic equation: distinct roots → A r_{1}^{n} + B r_{2}^{n}; repeated → (A + B n) r^{n}.
• Hanoi T_{n} = 2^{n} - 1; Fibonacci F_{n} = \frac{(\varphi^{n} - \psi^{n})}{\sqrt{5}}.
• Master theorem: compare d with \log_{b} a.

Chapter summary

• Induction proves infinitely many statements with two finite checks; strong induction is the right tool when the step needs several earlier cases.
• Recursive definitions give structures and programs; structural induction proves their properties.
• Linear recurrences are solved through the characteristic equation; non-homogeneous ones add a particular solution.
• The master theorem gives the cost of divide-and-conquer algorithms at a glance.

Practice

1. Prove by induction: 1^{2} + 2^{2} + \ldots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}.
2. Prove: 3 divides n^{3} - n for all n \geq 1 (induction, or factorisation).
3. Prove: 2^{n} \geq n + 1 for all n \geq 0.
4. Solve a_{n} = 3 a_{n-1} - 2 a_{n-2} with a_{0} = 2 ,\ a_{1} = 3.
5. Solve a_{n} = 6 a_{n-1} - 9 a_{n-2} ,\ a_{0} = 1 ,\ a_{1} = 6.
6. Solve a_{n} = 2 a_{n-1} + 3 ,\ a_{0} = 1.
7. How many bit strings of length 6 have no two consecutive 1s?
8. Apply the master theorem to T (n) = 4 T \left( \frac{n}{2} \right) + n ,\ T (n) = 2 T \left( \frac{n}{2} \right) + n^{2} ,\ T (n) = 9 T \left( \frac{n}{3} \right) + n^{2}.
9. Prove that every integer ≥ 14 can be written as 3 a + 8 b (non-negative a ,\ b) by strong induction.
10. Find the number of moves for the Tower of Hanoi with 6 discs and write the recursive algorithm.

Answers and worked solutions

1. Base n = 1: 1 = 1·2·3/6 ✓. Step: \frac{k (k + 1) (2 k + 1)}{6} + (k + 1)^{2} = \frac{(k + 1) [k (2 k + 1) + 6 (k + 1)]}{6} = \frac{(k + 1) (2 k^{2} + 7 k + 6)}{6} = \frac{(k + 1) (k + 2) (2 k + 3)}{6} ✓. ∎

2. n^{3} - n = (n - 1) n (n + 1), a product of three consecutive integers, so one is divisible by 3. Induction: (k + 1)^{3} - (k + 1) = (k^{3} - k) + 3 (k^{2} + k). ∎

3. Base 1 \geq 1. Step: 2^{k+1} = 2 \cdot 2^{k} \geq 2 (k + 1) = 2 k + 2 \geq k + 2. ∎

4. r^{2} − 3r + 2 = 0 \Rightarrow r = 1 ,\ 2. a_{n} = A + B \cdot 2^{n} ;\ A + B = 2; A + 2B = 3 \Rightarrow B = 1 ,\ A = 1: a_{n} = 1 + 2^{n}. (a_{2} = 9 - 4 = 5 = 1 + 4 ✓)

5. (r - 3)^{2} = 0 \Rightarrow a_{n} = (A + B n) 3^{n} ;\ A = 1 ;\ 3 (1 + B) = 6 \Rightarrow B = 1: a_{n} = (1 + n) 3^{n}. (a_{2} = 36 - 9 = 27 = 3·9 ✓)

6. Particular: a = 2 a + 3 \Rightarrow a = - 3. a_{n} = A \cdot 2^{n} - 3 ;\ a_{0} = A - 3 = 1 \Rightarrow A = 4: a_{n} = 4 \cdot 2^{n} - 3 = 2^{n+2} - 3. (a_{1} = 5 ✓)

7. s_{n} = s_{n-1} + s_{n-2} with s_{1} = 2 ,\ s_{2} = 3: 2, 3, 5, 8, 13, 21 for n = 6.

8. 4 T \left( \frac{n}{2} \right) + n: \log_{2} 4 = 2 > 1 \Rightarrow \Theta (n^{2}). 2 T \left( \frac{n}{2} \right) + n^{2}: \log_{2} 2 = 1 < 2 \Rightarrow \Theta (n^{2}). 9 T \left( \frac{n}{3} \right) + n^{2}: \log_{3} 9 = 2 = d \Rightarrow \Theta (n^{2} \log n).

9. Base: 14 = 3·2 + 8, 15 = 3·5, 16 = 8·2. Step: for k + 1 \geq 17 ,\ k - 2 \geq 15 can be written as 3 a + 8 b by hypothesis; add one 3 to get k + 1. ∎

10. T_{n} = 2^{n} - 1 = 63 moves. hanoi(n, from, to, via): if n = 0 return; \mathrm{hanoi} ( n - 1, from, via, to); move disc n from → to; \mathrm{hanoi} ( n - 1, via, to, from).

Model answers: medium (5 marks) and long (10 marks) questions

Q1 (5 marks). Prove by mathematical induction that 1 + 3 + 5 + \ldots + (2 n - 1) = n^{2} for all n \geq 1.

Introduction. Induction proves a statement P (n) for every integer n \geq 1 in two steps: a base case and an inductive step.

Base case. For n = 1 the left side is 1 and the right side is 1^{2} = 1, so P (1) is true.

Inductive hypothesis. Assume P (k) holds for some k \geq 1: 1 + 3 + \ldots + (2 k - 1) = k^{2}.

Inductive step. Add the next odd number 2 (k + 1) - 1 = 2 k + 1 to both sides: 1 + 3 + \ldots + (2 k - 1) + (2 k + 1) = k^{2} + 2 k + 1 = (k + 1)^{2}. This is P (k + 1).

Conclusion. P (1) is true and P (k) implies P (k + 1), so by the principle of mathematical induction P (n) holds for all n \geq 1.

Check n = 4 gives 1 + 3 + 5 + 7 = 16 = 4^{2}.

Q2 (10 marks). Solve the recurrence a (n) = 5 a (n - 1) - 6 a (n - 2) with a (0) = 1 ,\ a (1) = 4, and explain how divide-and-conquer recurrences and the Tower of Hanoi recurrence are solved.

Introduction. A recurrence relation defines each term from earlier terms. Linear recurrences with constant coefficients are solved by the characteristic equation.

Linear recurrence.

1. Characteristic equation. Try a (n) = r^{n}: r^{2} = 5r − 6, so r^{2} − 5r + 6 = 0.
2. Roots. (r - 2) (r - 3) = 0 gives r = 2 and r = 3, distinct.
3. General solution. a (n) = A \cdot 2^{n} + B \cdot 3^{n}.
4. Initial conditions. a (0) = A + B = 1 and a (1) = 2A + 3B = 4. Subtracting twice the first equation from the second gives B = 2, so A = - 1.
5. Answer. a (n) = 2 \cdot 3^{n} - 2^{n}. Check: a (2) = 5·4 − 6·1 = 14 and 2·9 − 4 = 14 ;\ a (3) = 5·14 − 6·4 = 46 and 2·27 − 8 = 46.

Other recurrences.

6. Tower of Hanoi. H (n) = 2 H (n - 1) + 1 with H (0) = 0 gives H (n) = 2^{n} - 1; with 10 disks, 1,023 moves.
7. Divide and conquer. T (n) = 2 T \left( \frac{n}{2} \right) + n (merge sort). Expand the recursion tree (Figure 4.1): \log_{2} n levels, n work each, so T (n) = \Theta (n \log n).
8. Repeated roots. If the characteristic equation has a double root r, the solution is (A + B n) r^{n}.

Recurrence	Solution	Use
a (n) = 5 a (n - 1) - 6 a (n - 2)	2 \cdot 3^{n} - 2^{n}	linear, distinct roots
H (n) = 2 H (n - 1) + 1	2^{n} - 1	Tower of Hanoi
T (n) = 2 T \left( \frac{n}{2} \right) + n	\Theta (n \log n)	merge sort

Conclusion. The characteristic equation solves constant-coefficient recurrences exactly; recursion trees give the order of growth of divide-and-conquer algorithms.