Induction for Beginners

Krzysztof R. Apt
CWI and University of Amsterdam
July 28, 2011

A friend of mine claims that he is 13 Indian. I told him that it is impossible. He replied: “Of
course, it is possible. My father is 13 Indian and my mother is 13 Indian, so I am also 31 Indian.”
Are you convinced? I am not. But could somebody be 15 Indian? It also sounds impossible.
On the other hand, to be 14 Indian is clearly possible: it happens when exactly one of the four
grandparents is Indian. Clearly, 18 is also possible.
And so is 58 . Indeed, just take an Indian mother and a father who is 14 Indian. Then to
compute the fraction for their child we take the average of the fractions of the parents and get
1 5
1+ 4 4 5
= =
2 2 8
Can we determine precisely the fractions f for which one can be f Indian? Yes, we can, but
you will have to wait for the answer till the end of this note. In the meantime you can check
what your friends think of the claim of my (partly) Indian friend.

Induction and functions

First, consider the following simple problem.

Problem 1 Take the function f defined as follows:

f (1) = 2,
f (n + 1) = 2 · f (n).

So
f (2) = 2 · f (1) = 4,
f (3) = 2 · f (2) = 8,
f (4) = 2 · f (3) = 16,
etc. It somehow looks that
f (n) = 2n . (1)
We just checked it for n = 1, 2, 3, 4. But how can we prove it for all natural numbers n ≥ 1?
We shall use for it the induction principle:

1
 • We first prove it for n = 1.
This step is called the induction base.

• Then we assume that it is already true for n and prove it for n + 1.

This step is called the induction step.

Once we prove these two facts we can conclude that the above equality (1) is true for all
n ≥ 1.
But equality (1) is clearly true for n = 1: it is just part of our assumptions. So the induction
base is true.
Suppose now that equality (1) is true for some n. Then we have

f (n + 1) = 2 · f (n) = 2 · 2n = 2n+1 .

So we proved the induction step. We conclude that, indeed, equality (1) is true for all n ≥ 1.
You may be interested to know that the above two line definition of the function f is a legal
program in the programming language Hugs. Here is an example interaction with its system,
where the file f.hs consists of the definition of f :

Hugs> :load f.hs

Main> f(10)
1024

Exercise 1 Consider the function f such that

f (1) = 3,
f (n + 1) = 3 + f (n).

Prove that for all n ≥ 1

f (n) = 3 · n.
2

Induction and properties

So far we dealt only with functions. But we can also use induction to prove some properties.
Here is an example.

Problem 2 Note the following intriguing equalities:

1=1
1+3=4
1+3+5=9
1 + 3 + 5 + 7 = 16
1 + 3 + 5 + 7 + 9 = 25

2
 Do you see the pattern? It looks like the following property is true:

the sum of the first n odd numbers is n2 . (2)

Let us prove this statement by induction.

First, we need to identify precisely the n+1st odd number. Note that the second odd number,
so 3, equals 2 · 2 − 1, the third odd number, so 5, equals 2 · 3 − 1, and so on. In general, the
n + 1st odd number equals 2(n + 1) − 1 = 2n + 1. (Actually, a precise proof of this statement
proceeds by induction.)
The induction base, so when n = 1, is clearly true. To prove the induction step assume that
our property (2) holds for some n ≥ 1. Denote the sum on the left-hand side by S(n).
By the above observation about the n + 1st odd number we have

S(n + 1) = S(n) + 2n + 1.

But we assumed that the property is true for n, so we have

S(n) = n2 ,

and hence
S(n + 1) = n2 + 2n + 1 = (n + 1)2 .
So we proved the induction step.
Hence, by induction, property (2) holds for all n ≥ 1. 2

Exercise 2 Consider a Wimbledon tennis tournament. So in the half finals 4 players are left, in
the quarter finals 8 players are left. Before then there were 16 players and before that 32. And
so on. This tournament structure is a complete binary tree. In Figure 1 we drew, as an example
the complete binary tree with the last 4 female players in 2010. So in the semi finals Williams
won against Kvitova, and Zvonareva won against Pironkova. Subsequently Williams won the
final against Zvonareva.

S. Williams

S. Williams V. Zvonareva

S. Williams P. Kvitova V. Zvonareva T. Pironkova

Figure 1: Women semi finals of Wimbledon 2010

In this tree there are 3 levels, 4 leaves (players) and 7 nodes. If there were 4 levels, there
would be 8 leaves and 15 nodes.
Prove that a complete binary tree with n ≥ 1 levels has 2n−1 leaves and 2n − 1 nodes. 2

3
Exercise 3 Here is a problem using which you can trick your math teacher.
Sometimes the number of players is not a power of 2. Then the resulting binary tree is not
complete. This is for instance the case when there are 107 players in the tournament. How
many matches are then needed to select the winner?
You can find the answer at the end of these notes. 2

It is important to realize that not all problems ‘about n’ have to be proved by induction.

Problem 3 Consider for instance the following property

2n + 1 < n2 . (3)
that holds for n ≥ 3. One can prove it by induction, but it is not needed. First, recall that

(n − 1)2 = n2 − 2n + 1.

So we rewrite the above inequality as

2 < n2 − 2n + 1,

and finally as
2 < (n − 1)2 .
Now the last inequality is clearly true for n ≥ 3, since the right-hand side is then at least 22 .
2

Problem 4 We shall now use inequality (3) from Problem 3 to prove the inequality

n2 < 2n . (4)

But is it true? The answer is: “No.” Indeed, for n = 2 both sides equal 4. Moreover, for
n = 3 we get 9 < 8, which is also false, and for n = 4 we get 16 < 16, which is again false.
Instead of giving up, let us check this property for a few more numbers:

n left-hand right-hand
side side
5 25 32
6 36 64
7 49 128
8 64 256
9 81 512
10 100 1024

So, curiously, our property begins to look true, but only starting with n = 5. Can we prove
it? The answer is: “Yes”, and you guessed it: we prove it by induction.

4
Induction base. n = 5.
In fact, we checked it already.
Induction step.
We assume that it is true for some n ≥ 5 and we show that it is true n + 1. To start with,
note that by the assumption we have:

2 · n2 < 2 · 2n = 2n+1 .

So far, so good. We still need to prove

(n + 1)2 < 2 · n2

and then we are done.

But we have n > 2, so we get by (3)

(n + 1)2 = n2 + 2n + 1 < n2 + n2 = 2 · n2 .

Which means that we proved the induction step. Hence, we proved by induction that (4) holds
for all n ≥ 5.

Exercise 4 Note that 61 = 6, 62 = 36, 63 = 216 and 64 = 1296. It looks that for all n ≥ 1 the
last digit of 6n is 6. Prove it. 2

Exercise 5 Find the error in the proof of the following ‘result’.

‘Theorem’ Every natural number n ≥ 2 is even.
Proof. We prove by induction the following property:

Every natural number k such that 2 ≤ k ≤ n is even.

Induction base. n = 2.
There is only one number to check, namely 2, so this step is obvious.
Induction step.
We assume that the above property holds for some n ≥ 2. We prove it for n + 1. The only
new natural number we need to consider is n + 1. But n + 1 can be written as a sum k + l of
two numbers such that both k ≤ n and l ≤ n. Since the property holds for n, both k and l are
even. So their sum n + 1 is also even. 2

The towers of Hanoi puzzle

We now discuss the following puzzle:

Consider three pegs, A, B and C, and n different disks put on peg A by the decreas-
ing size, see for instance Figure 2 for n = 5. Your task is to move all the disks from
A to B in such a way that at no time a larger disk is placed upon a smaller one. You
can use C as an auxiliary peg.

5
 1
2
3
4
5

Figure 2: Towers of Hanoi for n = 5

Here is, for example a solution for n = 3:

move top disk from A to B

move top disk from A to C
move top disk from B to C
move top disk from A to B
move top disk from C to A
move top disk from C to B
move top disk from A to B

We depict this sequence of seven steps on the next two pages.

6
1
2
3

2
3 1

3 1 2

1
3 2

7
 1
3 2

1 3 2

2
1 3

1
2
3

8
 But can one do this for an arbitrary n ≥ 1? The answer is yes and we prove the following
result.

Theorem 1 For every n ≥ 1 there is a solution for the Hanoi towers puzzle.

Proof. We prove the theorem by induction.

Induction base. n = 1.
Obvious: just move the (only) disk from A to B.
Induction step.
Suppose now that we know how to solve the puzzle for some n ≥ 1, that is we know how to
generate the appropriate sequence of disk moves. We now show that it is possible to solve the
puzzle for n + 1. We proceed as follows:

• we move the top n disks from A to C using B as an auxiliary peg,

• we move the largest disk (which is now free) from A to B,

• we move n disks from C to B using A as an auxiliary peg.

These three steps for n = 5 are depicted on the next page.

Note that in the last step the fact that there is initially a disk on peg B is not a problem, since
this disk is larger than the remaining n disks.
So we conclude by induction that for every n ≥ 1 it is possible to solve the puzzle. 2

9
 1
2
3
4
5

1
2
3
5 4

1
2
3
5 4

1
2
3
4
5

10
 The puzzling thing is that this proof does not generate an explicit sequence of moves that
need to be performed. But, before you conclude that the proof of the above theorem is not very
helpful consider the following.
The above procedure can be easily encoded in a programming language. For instance, here
is the way one can encode it in the programming language Prolog:
move(1,A,B,C) :-
write(’move top disk from ’),
write(A),
write(’ to ’),
write(B),
nl. % newline
move(M,A,B,C) :-
M>1,
N is M-1,
move(N,A,C,B),
move(1,A,B,C),
move(N,C,B,A).
Even if you don’t know Prolog (nobody is perfect) you have to agree that this program looks
suspiciously similar to the way we proved our Theorem 1, especially the last three lines. You
might be interested to know that the above solution for n = 3 on page 6 was in fact generated
by this very program.

A tiling puzzle
Consider now Figure 3.

Figure 3: A tiling using trominoes

It represents an 8 by 8 chessboard with the white square removed which is tiled by 3-piece
tiles in the form of the letter L. Can this be done for an arbitrary chessboard with one square
removed?

11
 The following theorem due to S.W. Golomb provides a positive answer to our question and
shows more. Below we call the 3-piece tiles in question trominoes and a chessboard with an
arbitrary square removed a mutilated chessboard.

Theorem 2 Every 2n by 2n mutilated chessboard can be tiled by trominoes.

Proof. The proof is based on a beautiful induction argument.

Induction base. n = 1.
Obvious.
Induction step.
Assume the claim is true for some n. Consider an 2n+1 by 2n+1 mutilated chessboard. Di-
vide it into four 2n by 2n chessboards. The removed square lies in one of these four chessboards.
Remove now the center corner from each of the remaining three 2n by 2n chessboards. This
way we have now four 2n by 2n mutilated chessboards.
By our assumption we can tile each of them by trominoes. We now add one tromino to cover
the gap formed in the center by the three removed squares. (In Figure 3 it is the tromino that
forms a square together with the removed white square.) This leads to a tiling of the considered
mutilated chessboard.
So we conclude our claim by induction . 2

An interesting thing about this proof is that in the induction step, in order to find a solution
for one specific 2n+1 by 2n+1 mutilated chessboard, we assumed that a solution exists for all
mutilated chessboards of size 2n by 2n .

Induction versus recursion

When discussing induction one often mentions recursion. The latter term is often used inter-
changingly, like in a statement: ‘this function was defined inductively’ versus ‘’this function
was defined by recursion’. But these statements differ. Intuitively, induction starts with an in-
duction base and proceeds ‘forward’, while recursion proceeds ‘backward’ and, as a result may
continue forever if it does not ‘hit’ the base case.
To clarify this point consider the following innocently looking definition of a function f:
f(1) = 1
f(n+1) = 2*f(f(n))
We wrote it on purpose in the teletype font to stress that we shall now view it as a Hugs
program (written in the file f.hs) , so that we can use a Hugs system to compute its values.
We have:
Main> f(1)
1
Main> f(2)
2
Main> f(3)
4

12
 But consider now what happens when we want to compute the value of this function for
n = 4:

Main> f(4)

ERROR - Control stack overflow

Upon closer look this is not so surpring. To compute f (4) we need to compute 2 · f (f (3)).
So we compute first f (3), which is 4, and then apply to it f . Hence when computing f (4) we
end up computing f (4) again. This process clearly does not terminate, which explains the error:
in an attempt of computing the result the system eventually run of out space.
When discussing recursion one sometimes talks about the ‘Droste effect’ and refers to the
famous picture of a Droste cacao box given in Figure 4. Note that the recursion in this picture
intentionally does not terminate. In computer science recursion usually refers to a function or
procedure defined in terms of itself. For example, the above defined function f is a recursive
function, while our Prolog program that solves the towers of Hanoi puzzle employs a recursive
procedure move.

Figure 4: The Droste effect

Being partly Indian

Finally, let us return to my friend, who is partly Indian. We noticed already that one can be
1/8 and 5/8 Indian. Can we formulate a conjecture which fractions are possible here? First we
prove the following expected result.

k
Theorem 3 For every n ≥ 1 and every k ≤ 2n it is possible to be 2n
Indian1 .
1
Fractions of this form are called dyadic fractions.

13
Proof. We proceed by induction.
Induction base. n = 1.
Since 21 = 2, we have three cases to consider k = 0, k = 1 and k = 2. But all three
situations are clearly possible, so to be no Indian at all, to be 50% Indian and to be 100%
Indian.
Induction step.
We assume the claimed property is true for some n ≥ 1. Take some k ≤ 2n+1 . We show
k
that it is possible to be 2n+1 Indian.
Indeed, if k is even, say k = 2l, then
k 2l l
= = ,
2n+1 2n+1 2n
k
so to be 2n+1 Indian is the same as to be 2ln Indian and we assumed that the property holds for
n.
Further, if k is odd, say k = 2l + 1, then first we ‘produce’ a mother who is 2ln Indian and
1
take a father who is 2n+1 Indian. Then their child is
l 1
2n
+ 2n 2l 1 2l + 1 k
= + = = n+1
2 2n+1 2n+1 2n+1 2
Indian. So we proved the induction step.
We conclude by induction that the claimed property is indeed true for all n ≥ 1. 2

But perhaps there are some other fractions that we forgot about? The answer is “No”.
Namely, we have the following result.
k
Theorem 4 If one is f Indian, then for some n ≥ 1 and k ≤ 2n we have f = 2n
.

Proof. We consider a family tree of the person who claims to be f Indian. We prove that
everybody in this tree is 2kn Indian for some n ≥ 1 and k ≤ 2n .
We proceed —how else?— by induction. We start with the two parents who are the ‘founders’
of this family tree. Each of them has no ancestors so is either 0% or 100% Indian2 . So for the
founders the claim holds: just take n = 1 and k = 0 or k = 1.
Suppose now that the claim holds for all children at a given level, say n, of this family tree.
Consider now a child at a level n + 1. By assumption his parents are at level n, so for some
k ≤ 2n and l ≤ 2n they are 2kn and 2ln Indian. Hence their child is
k l
2n
+ 2n k+l
=
2 2n+1
Indian. Moreover, k + l ≤ 2n + 2n = 2n+1 .
So we proved the claim by induction. 2
2
This is where my views differ from those of my Indian friend. He used a recursive definition without a base
case.

14
 This disproves the claim of our friend that he is 31 Indian because for no k and n the equality
1
3
= 2kn can hold, since 3 does not divide 2n .
This seems likes the end of the story. But when I told this problem to a colleague of mine,
Freek Wiedijk, he was not convinced. He came up with the following scenario. Suppose that
a 100% Indian woman marries twice, each time a white man. From each marriage she has one
child, one boy and one girl. Each of these children is then 50% Indian. Then these children
marry and have a child. Their child, say Sunil, is then also 50% Indian. But is it? You can
also look at it differently: Sunil has only 3 grandparents, two white grandfathers and one 100%
Indian grandmother. So Sunil is 31 Indian. So in the end it all depends whether you count the
percentages by considering the parents, grandparents or some farther ancestors.

Exercise 6 Speaking about 31 . Suppose that we have three buckets of 2 liters, with in each
bucket 1 liter of paint of a different colour. Is it possible to mix these paints so that one gets a
mixture in which one has 13 of each colour?
Because the buckets have no markings, the only possible actions are poring paint from one
bucket to another, until one fills it completely. So in the beginning one can only pore one paint
into a bucket with another another. From that moment on the only meaningful action is poring
1 liter of paint from a bucket that contains 2 liters to a bucket that contains 1 liter.
Hint. This puzzle has something to do with the dyadic fractions.

PS. Ah, yes, I would have completely forgotten: here is a solution to Exercise 3. This problem
has nothing to do with induction (that why we put it just above Problem 3). The answer is 106.
Indeed, in each match exactly one player is eliminated and one needs to eliminate 106 players
to select the winner.

Acknowledgements
I would like to thank Dion Gijswijt, Femke van Raamdsonk and Freek Wiedijk for helpful
discussions.

15