Mathematics for Computer Science 201-N11 • CEGEP, Montreal

Revision sheet: induction and recursion (201-N11)

Induction is the first reasoning in the course where the WRITE-UP counts as much as the idea: two steps, two model sentences, and a mark lost every time one of them is missing. This sheet covers those sentences, then their algorithmic counterpart, the cost of a recursive function.

It is written for CEGEP students in computer science programs and for anyone who comes to algorithms through mathematics. The corrected exercise set on the same chapter then puts every reflex to the test.

Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next, tells you which chapter to tackle next and lets you ask for the method or exercise you are missing. Create your space, an email is enough.

The thread of the chapter

The inductive step is an IMPLICATION to prove, not a property to assume true. Marks are lost by writing “assume the property true for every $n$ ”, which already assumes the result, and by forgetting the base case, which is the only thing that ties the chain to the ground.

This chapter is part of 201-N11, Mathematics for Computer Science

What is on this sheet

1. The essentials
2. The mistakes that cost marks
3. Which method to choose
4. How the answer is expected to be written
5. Check before you hand in
6. The typical problem, taken apart
7. Learn by heart
8. Frequently asked questions

Topics covered

Proof by mathematical induction
Base case
Inductive step
Strong induction
Linear recurrence relation
Characteristic equation
Recursive function
Recursive base case
Call stack
Algorithmic complexity
Memoization
Divide and conquer

The essentials

Two steps, and the inductive step is an IMPLICATION

• BASE CASE: $P(n_{0})$ is true, checked by computation, not asserted.
• INDUCTIVE STEP: for every $k\geq n_{0}$ , $P(k)$ IMPLIES $P(k+1)$ . You fix $k$ , assume $P(k)$ , and prove $P(k+1)$ .
• Conclusion: $P(n)$ is true for every $n\geq n_{0}$ .
• You NEVER assume that $P(k)$ is true for every $k$ : that would be assuming exactly what you want to prove.

The base case knocks over the first domino; the inductive step guarantees that every domino that falls knocks over the next one. Together they knock over the whole row.

The correct inductive-step sentence is: “Let $k\geq n_{0}$ be an integer such that $P(k)$ is true. Let us show that $P(k+1)$ is also true.” Copy it as is; it is worth a mark on every test.

The two typical failures, each one killing a step

• INDUCTIVE STEP WITHOUT A BASE CASE: the property “ $n=n+1$ ” is inherited, since $k=k+1$ implies $k+1=k+2$ . Yet it is false everywhere, for lack of a starting rank.
• CHECKS WITHOUT AN INDUCTIVE STEP: $n^{2}+n+41$ is prime for $n$ from $0$ to $39$ , and equals $41^{2}$ at $n=40$ . Forty cases prove nothing.
• These two failures say the same thing: each of the two steps is necessary, and neither is sufficient.
• On an exam, the forgotten base case is the most frequent mistake, and the easiest to avoid: two lines of computation.

On the left, the chain is perfect but nobody pushes: nothing falls. On the right, someone pushed, but the chain breaks at rank

40

: the checks are not enough.

A TWO-STEP induction requires TWO base cases, and a strong induction makes do with one when the base case is unique: the number of base cases is the number of earlier ranks used.

From recursive sequence to recursive function

• A recursive function TERMINATES if it has a BASE CASE and if every call is made on a strictly smaller argument that eventually reaches it.
• The CALL STACK keeps one record per call in progress: hence the limit of about a thousand nested calls in Python.
• Standard costs: $T(n)=T\left(\frac{n}{2}\right)+1$ gives $\log_{2}n$ , binary search. $T(n)=2T\left(\frac{n}{2}\right)+n$ gives $n\log_{2}n$ , merge sort.
• $T(n)=2T(n-1)+1$ gives $2^{n}-1$ , the Towers of Hanoi. $T(n)=T(n-1)+T(n-2)+1$ gives $2F_{n+1}-1$ , the naive version of Fibonacci.

The four costs of the chapter on the same scale:

\log_{2}n

stays flat,

n

rises gently,

n\log_{2}n

follows close behind, and

2^{n}

already leaves the frame before

n=7

Two-step linear recurrence: the characteristic equation

• For $u_{n+2}=au_{n+1}+bu_{n}$ , solve $r^{2}=ar+b$ , called the characteristic equation.
• Two distinct roots $r_{1}$ and $r_{2}$ : $u_{n}=Ar_{1}^{n}+Br_{2}^{n}$ , the TWO initial conditions fixing $A$ and $B$ .
• Double root $r$ : $u_{n}=(A+Bn)r^{n}$ .
• On $u_{n+2}=u_{n+1}+u_{n}$ , this gives Binet's formula for Fibonacci, with the golden ratio as a root.

The Fibonacci terms (dots) follow the curve

\frac{\varphi^{n}}{\sqrt{5}}

: the

r_{2}^{n}

term of Binet's formula dies out, and

F_{n}

is its rounding.

The system in $A$ and $B$ is solved with $u_{0}$ AND $u_{1}$ . A single condition leaves a family of solutions, and handing in one of them at random costs half the question.

The mistakes that cost marks

These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.

1. Assuming the property true for every $n$

1 to 2 marks, for every induction on the test

What not to write

“Assume that $P(n)$ is true for every $n$ , and let us show $P(n+1)$ .”

What to write

“Let $k\geq n_{0}$ be an integer such that $P(k)$ is true. Let us show that $P(k+1)$ is also true.”

Why: Assuming the property true for every $n$ means assuming the result: the proof no longer proves anything. You fix ONE rank and assume the property at that rank only.

2. Skipping the base case because it is obvious

the whole proof, since the inductive step alone proves nothing

What not to write

“The inductive step is established, so the property is true for every $n$ .”

What to write

“Base case: $P(1)$ is checked by computation. Inductive step: ... Conclusion: by induction, $P(n)$ is true for every $n\geq 1$ .”

Why: The property “ $n=n+1$ ” is perfectly inherited and false everywhere. Without a rank where the chain touches the ground, the inductive step knocks over dominoes that do not exist.

3. Taking checks for a proof

the whole question

What not to write

“ $n^{2}+n+41$ is prime for $n=0$ , $1$ , $2$ , ..., $10$ : so the property is true.”

What to write

“No number of cases proves a property on $\mathbb{N}$ . Here the formula is prime up to $n=39$ and equals $41^{2}=1681$ at $n=40$ .”

Why: It is Euler's historic counterexample, chosen precisely because forty cases look like overwhelming evidence. Only the inductive step covers infinitely many ranks.

4. A single base case for a two-step relation

2 marks, and an inductive step that cannot get started

What not to write

“ $u_{n+2}=u_{n+1}+2u_{n}$ : I check $u_{0}$ , then I do the inductive step.”

What to write

“You need TWO base cases, $u_{0}$ and $u_{1}$ , as many as there are earlier ranks in the relation, and the inductive step assumes $P(k)$ AND $P(k+1)$ .”

Each term rests on the TWO previous ones (grey arcs): to start the chain, you must push

u_{0}

AND

u_{1}

Why: The inductive step goes from two consecutive ranks to the next one: without two starting points, it has nothing to stand on. The number of base cases is the number of earlier ranks used.

5. Writing a recursive function with no reachable base case

the whole termination question, and a program that crashes

What not to write

“ $f(n)$ calls $f(n-2)$ , with $f(0)=1$ as the only base case.”

What to write

“For odd $n$ , the chain of calls never meets $0$ : you need a second base case, $f(1)$ , or a guaranteed decrease to $0$ .”

f(n)

calls

f(n-2)

: starting from

4

, you reach the base case

0

; starting from

5

, the calls skip

0

and go down forever.

Why: Termination requires two things: a base case, and an argument that strictly decreases UNTIL it reaches it. The first without the second produces a stack overflow, not a mathematical error.

6. Believing that a naive Fibonacci recursion is linear

the whole complexity question

What not to write

“ $f(n)$ makes two calls, so about $2n$ calls in all.”

What to write

“The number of calls satisfies $T(n)=T(n-1)+T(n-2)+1$ , so $T(n)=2F_{n+1}-1$ : it is EXPONENTIAL, and $f(40)$ already requires more than three hundred million calls.”

The call tree of

f(4)

recomputes

f(2)

twice and

f(1)

three times: the subproblems OVERLAP, and that is exactly what memoization removes.

Why: Two calls per level over a depth of $n$ make a tree, not a chain. What counts is the number of LEAVES, and it grows like the golden ratio to the power $n$ .

7. Believing that memoization speeds up any recursion

1 to 2 marks, and a wrong algorithmic conclusion

What not to write

“Hanoi is exponential, so I will memoize it.”

What to write

“Memoization only helps if the subproblems OVERLAP. In Hanoi, every move is distinct: the $2^{n}-1$ moves are the intrinsic cost of the problem and nothing will improve it.”

Why: Memoization removes RECOMPUTATIONS, not work. Naive Fibonacci recomputes the same values; Hanoi produces an output of length $2^{n}-1$ that no trick will shorten.

8. Confusing the number of calls with the depth of the stack

1 to 2 marks, and a wrong diagnosis

What not to write

“The Fibonacci recursion makes millions of calls, so the stack overflows.”

What to write

“The DEPTH of the stack is $n$ , not the total number of calls: the calls follow one another, they do not all coexist. It is a deep recursion, a chain of $n$ nested calls with $n$ very large, that overflows the stack.”

\mathrm{fib}(4)

makes

9

calls, but the stack never holds more than the current branch (blue): its depth is

4

Why: The stack only holds the calls IN PROGRESS. A tree of three hundred million nodes has only about forty levels, whereas a simple recursive loop over $10^{6}$ overflows in Python after a thousand calls.

Which method to choose

Which form of induction for which property

Look at which earlier ranks rank $n$ depends on. That, and nothing else, sets the number of base cases and the form of the hypothesis.

If $P(k)$ is enough to get $P(k+1)$ → ordinary induction, one base case

Example: $\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$
If the relation involves $u_{n+1}$ AND $u_{n}$ → two-step induction, TWO base cases, hypothesis covering two consecutive ranks

Example: $u_{n+2}=u_{n+1}+2u_{n}$
If you split the object into pieces of UNKNOWN sizes → STRONG induction: the hypothesis covers all ranks from $n_{0}$ to $k$

Example: every integer greater than $1$ has a prime divisor

This is the typical case in computer science: a list cut into two pieces of arbitrary sizes forces you to assume the property for all smaller sizes.
If the property is an INEQUALITY → same scheme, but start from the left side and bound it, never starting from the inequality to be proved

Example: $2^{n}\geq n^{2}$ for $n\geq 4$
If the property is a DIVISIBILITY → write the hypothesis in the form $u_{k}=m\times q$ , then bring out the factor $m$ in $u_{k+1}$

Example: $7^{n}-1$ is divisible by $6$

In every case, the conclusion is written: “By induction, $P(n)$ is true for every $n\geq n_{0}$ .” It is worth a mark, and it is missing from one test in three.

Which cost for which form of recurrence relation

Read the relation $T(n)$ and look for two things: by how much the argument decreases, and how many calls are made at each level.

Each step of binary search divides the search zone by TWO: four steps are enough for

16

cells, which is exactly

\log_{2}16

. This is the form

T(n)=T\left(\frac{n}{2}\right)+1

If $T(n)=T\left(\frac{n}{2}\right)+1$ → $\log_{2}n$ , logarithmic cost

Example: binary search in a sorted array
If $T(n)=2T\left(\frac{n}{2}\right)+n$ → $n\log_{2}n$

Example: merge sort, quicksort on average
If $T(n)=T(n-1)+1$ → $n$ , linear cost

Example: recursive sum of the elements of a list
If $T(n)=2T(n-1)+1$ → $2^{n}-1$ , INTRINSIC exponential cost

Example: Towers of Hanoi

Here the output itself has exponential length: no optimization can do better, and memoization is useless.
If $T(n)=T(n-1)+T(n-2)+1$ → $2F_{n+1}-1$ , AVOIDABLE exponential cost

Example: naive Fibonacci, brought down to a linear cost by memoization

The question to ask in front of an exponential cost is always the same: do the subproblems OVERLAP? If so, memoization brings the cost down to the number of distinct subproblems; if not, the cost is that of the problem.

How the answer is expected to be written

A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.

Writing an induction for the marker

When to use it: Any property to be proved for every integer $n$ greater than or equal to some rank.

1 State the property with its rank: “For $n\geq 1$ , let $P(n)$ be: $\sum_{i=1}^{n}i^{3}=\left(\frac{n(n+1)}{2}\right)^{2}$ .”
2 BASE CASE, by computing both sides: “ $P(1)$ : on the left $1^{3}=1$ , on the right $\left(\frac{1\times 2}{2}\right)^{2}=1$ . $P(1)$ is true.”
3 INDUCTIVE STEP, fixing the rank: “Let $k\geq 1$ be such that $P(k)$ is true. Let us show $P(k+1)$ .”
4 Start from the LEFT side at rank $k+1$ , isolate the new term, replace using the hypothesis, then transform until you reach the expected right side.
5 CONCLUSION, named: “By induction, $P(n)$ is true for every $n\geq 1$ .”

Concluding sentence

By induction, for every integer $n\geq 1$ , $\sum_{i=1}^{n}i^{3}=\left(\frac{n(n+1)}{2}\right)^{2}$ .

The trap: Starting from the equality to be proved and transforming both sides until you get a true identity. That is reasoning backwards: the marker expects a computation that STARTS from the left side and ARRIVES at the right side.

Marking: Typically 1 mark for the computed base case, 1 mark for the correctly quantified inductive-step sentence, 2 marks for the computation, 1 mark for the conclusion.

Solving a two-step linear recurrence

When to use it: The problem gives $u_{n+2}=au_{n+1}+bu_{n}$ with $u_{0}$ and $u_{1}$ , and asks for an expression of $u_{n}$ .

1 Write the characteristic equation: “ $u_{n+2}=u_{n+1}+2u_{n}$ gives $r^{2}=r+2$ , that is, $r^{2}-r-2=0$ .”
2 Solve and state the case: “The roots are $r_{1}=2$ and $r_{2}=-1$ , distinct.”
3 Write the general form: “There exist $A$ and $B$ such that $u_{n}=A\times 2^{n}+B\times(-1)^{n}$ .”
4 Use BOTH initial conditions to form a system: “ $u_{0}=A+B=1$ and $u_{1}=2A-B=8$ .”
5 Solve, write the expression, then CHECK it on a third rank computed both ways.

Concluding sentence

For every $n\geq 0$ , $u_{n}=3\times 2^{n}-2\times(-1)^{n}$ .

The trap: Using a single initial condition and fixing the other constant at random. A system with two unknowns requires two equations, and a single one leaves a whole family of solution sequences.

Marking: 1 mark for the characteristic equation, 1 mark for the roots, 1 mark for the system, 1 mark for the final expression, checked.

Check before you hand in

Five minutes of checking recover more marks than one more problem started in a hurry.

Test the formula on the first three ranks

Compute both sides for $n_{0}$ , $n_{0}+1$ and $n_{0}+2$ . A wrong formula almost always shows itself by the second or third rank.

On $\sum i^{3}$ : $1$ , then $1+8=9=3^{2}$ , then $9+27=36=6^{2}$ . The squares $1$ , $9$ , $36$ confirm the formula before you even start the induction.
Check that the inductive step really uses the hypothesis

Reread the inductive computation and find the exact place where $P(k)$ was used. If the hypothesis is never used, the property can be proved directly, and induction is a detour.

In the computation of $\sum_{i=1}^{k+1}i^{3}$ , the hypothesis is used at the moment the sum of the first $k$ cubes is replaced by $\left(\frac{k(k+1)}{2}\right)^{2}$ . Without that substitution, there is no induction.
Count the base cases

As many base cases as there are earlier ranks in the relation. A two-step relation requires two, an ordinary induction only one.

$u_{n+2}=u_{n+1}+2u_{n}$ requires $u_{0}$ and $u_{1}$ . A single base case would not pin the sequence down: the relation alone is satisfied, for example, by every sequence of the form $A\times 2^{n}$ , whatever $A$ .
Check a stated cost on a small case

Run the algorithm by hand for $n=3$ or $n=4$ and count the operations. The number obtained must match the formula.

Hanoi with three disks requires seven moves, and $2^{3}-1=7$ . A count of eight signals a badly written decomposition.

The typical problem, taken apart

The Towers of Hanoi: proving $2^{n}-1$ moves

You have three pegs and $n$ disks of different sizes, stacked from largest to smallest on the first peg.

You move one disk at a time and never put a disk on a smaller one.

Prove by induction that moving the whole stack requires exactly $2^{n}-1$ moves.

Three pegs, a stack of disks from largest to smallest: you move one disk at a time, never onto a smaller one.

Step 1

For $n\geq 1$ , let $P(n)$ be the property: “moving a stack of $n$ disks requires exactly $2^{n}-1$ moves”.

Why

You name the property and its starting rank BEFORE any computation. An induction without a named property cannot be graded, and the marker cannot follow which rank each statement applies to.

Step 2

BASE CASE. For $n=1$ , a single disk moves in one move, and $2^{1}-1=1$ . So $P(1)$ is true.

Why

The base case is COMPUTED, not asserted. Two lines, one mark on the scheme, and it is the most often skipped step of the chapter.

Step 3

INDUCTIVE STEP. Let $k\geq 1$ be an integer such that $P(k)$ is true. Let us show that $P(k+1)$ is also true.

Why

You fix ONE rank $k$ and assume the property at that rank only. Writing “for every $k$ ” here would amount to assuming the result, and the proof would no longer prove anything.

Step 4

To move $k+1$ disks, you move the top $k$ disks to the free peg, which takes $2^{k}-1$ moves by the induction hypothesis; you move the large disk, $1$ move; you move the $k$ disks back onto the large one, another $2^{k}-1$ moves.

Why

This is the only moment the induction hypothesis is used, and it is used TWICE. Spotting it lets you check that the proof really is one, and not a disguised direct computation.

Step 5

Total: $\left(2^{k}-1\right)+1+\left(2^{k}-1\right)=2\times 2^{k}-1=2^{k+1}-1$ . So $P(k+1)$ is true.

Why

The computation starts from the decomposition and ARRIVES at the expected form. Starting from $2^{k+1}-1$ to land back on the decomposition would be reasoning backwards, which the marker rejects.

Step 6

CONCLUSION. By induction, for every $n\geq 1$ , moving $n$ disks requires exactly $2^{n}-1$ moves.

Why

The concluding sentence names the principle used and recalls the domain of validity. It is worth a mark and is missing from one test in three.

Step 7

Check: $n=3$ gives $2^{3}-1=7$ , which you get back by playing the game by hand; $n=4$ gives $15$ , and $n=10$ already $1023$ .

Why

A small case played by hand confirms the decomposition, and the large values show that the cost really is exponential: that is often the next question on the test.

The conclusion, written out

By induction, moving a stack of $n$ disks requires exactly $2^{n}-1$ moves, which is also the minimum number: the decomposition used is the only possible one.

The classic mistake on this problem: Writing the total $2^{k}-1+1+2^{k}-1=2^{k+1}$ , losing the $-1$ . The formula obtained would give $2$ moves for a single disk, which the base case contradicts at once: the check at $n=1$ catches this mistake in three seconds.

Learn by heart

• Two steps: a computed BASE CASE, then the INDUCTIVE STEP, which is an implication.
• The inductive-step sentence: “Let $k\geq n_{0}$ be such that $P(k)$ is true. Let us show $P(k+1)$ .”
• As many base cases as there are earlier ranks in the relation.
• Inductive step without a base case: “ $n=n+1$ ”. Cases checked without an inductive step: $n^{2}+n+41$ .
• A recursive function terminates if it has a base case AND an argument that decreases until it reaches it.
• $T\left(\frac{n}{2}\right)+1$ gives $\log_{2}n$ ; $2T\left(\frac{n}{2}\right)+n$ gives $n\log_{2}n$ ; $2T(n-1)+1$ gives $2^{n}-1$ .
• Memoization only helps if the subproblems OVERLAP.
• Characteristic equation $r^{2}=ar+b$ , then $u_{n}=Ar_{1}^{n}+Br_{2}^{n}$ with TWO initial conditions.

Frequently asked questions

How do you write the induction hypothesis correctly?

You fix a rank and assume the property true at that rank only: let k be greater than or equal to the starting rank and such that the property holds at rank k; let us show that it holds at rank k plus one. Writing that you assume the property true for every n would amount to assuming the result, and the proof would no longer prove anything.

Why do you need a base case if the inductive step is proved?

Because the inductive step alone proves nothing. The property n equals n plus one is inherited and false everywhere: if it were true at some rank, it would be true at the next one, but it is true at none. The base case is what ties the chain to the ground, and without it no domino falls.

How many base cases do you need for a two-step sequence?

Two, as many as there are earlier ranks used in the relation. A sequence defined by its two previous terms needs its first two terms to get started, and the induction hypothesis must cover two consecutive ranks. A single base case would let through sequences other than the one in the problem.

When does memoization speed up a recursive function?

Only when the subproblems overlap, that is, when the function recomputes the same values several times. That is the case of naive Fibonacci, which goes from an exponential cost to a linear one. It is not the case of the Towers of Hanoi, where every move is distinct and the exponential cost is that of the problem itself.

What is the difference between the number of calls and the depth of the stack?

The stack only holds the calls in progress, so its depth is the length of the longest chain of nested calls. The call tree of Fibonacci has millions of nodes but only about forty levels. Conversely, a simple linear recursion over a million elements exceeds the Python limit of a thousand nested calls.

Practise it

Corrected exercises: Induction and recursion, 201-N11

A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.

10 corrected exercises
100 points
150 minutes

Do the exercises

Something missing from this sheet? A method, a trap, an exercise to practise it, a mistake you spotted: tell me, I read every request.

Sending goes through your free space: that is how I can answer you and tell you when the exercise is added. An email is enough, no password. Create your space. Rather not create an account? Write to me directly.

Previous sheet Injective, surjective and bijective functions Next sheet Introduction to graphs and matrices

© Ahmed Squalli Houssaini. Revision sheet published at www.letuteurscientifique.ca/en/fiches/cegep-n11-induction-recursion. Free for personal and classroom use; republishing it elsewhere requires written permission (legal notice).

Looking for a 201-N11 tutor in Montreal?

Get in touch for a first session. We work on induction and recursion at the real level of the tests, from writing an inductive step to analyzing the cost of an algorithm.

Book a session WhatsApp

Site by Studio Squalli

Revision sheet: induction and recursion (201-N11)

The essentials

Two steps, and the inductive step is an IMPLICATION

The two typical failures, each one killing a step

From recursive sequence to recursive function

Two-step linear recurrence: the characteristic equation

The mistakes that cost marks

1. Assuming the property true for every nnn

2. Skipping the base case because it is obvious

3. Taking checks for a proof

4. A single base case for a two-step relation

5. Writing a recursive function with no reachable base case

6. Believing that a naive Fibonacci recursion is linear

7. Believing that memoization speeds up any recursion

8. Confusing the number of calls with the depth of the stack

Which method to choose

Which form of induction for which property

Which cost for which form of recurrence relation

How the answer is expected to be written

Writing an induction for the marker

Solving a two-step linear recurrence

Check before you hand in

The typical problem, taken apart

The Towers of Hanoi: proving 2n−12^{n}-12n−1 moves

Learn by heart

Frequently asked questions

How do you write the induction hypothesis correctly?

Why do you need a base case if the inductive step is proved?

How many base cases do you need for a two-step sequence?

When does memoization speed up a recursive function?

What is the difference between the number of calls and the depth of the stack?

Corrected exercises: Induction and recursion, 201-N11

See also

Looking for a 201-N11 tutor in Montreal?

1. Assuming the property true for every $n$

The Towers of Hanoi: proving $2^{n}-1$ moves