Mathematical Induction

*
Tarek Hajj Shehadi
April 2020

American University of Beirut

Department of Mathematics and Applied Statistics
MATH 211

* Undergraduate double majoring in Electrical and Computer Engineering and Applied

Mathematics at the American University of Beirut.

1
Contents
1 Introduction 3
1.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Formalization . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Alternative Base Case . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Finite Series Sum . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Recursion 7
2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Power Towers . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Continued Fractions and Square Roots . . . . . . . . . . . . . 9
2.4 Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . . . . 11

3 Strong Induction 12
3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Formalization . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2
1 Introduction
Quite often in mathematics we find ourselves wanting to prove a statement
that we think is true for every natural number n.

1.1 History
The earliest implicit traces of mathematical induction may be found in Eu-
clid’s proof that there are infinitely many primes and in Bhaskara’s many
works such as ”cyclic method”. A proof by mathematical induction was used
by Al-Fakhri for arithmetic sequences which was in turn used to prove the
Binomial theorem and Pascal’s triangle. None of these ancient mathemati-
cians, however, explicitly stated the induction hypothesis. Another similar
case was that of Maurolico who used the technique to prove that the sum
of n odd integers is n2 . During the 19th century, induction became more
rigoriously defined among mathematicians.

1.2 Definition
The simplest form of induction is called simple induction and the proof con-
sists of two steps :

Theorem 1 For every integer n ≥ 0 or n ≥ 1 we have :

1. The Initial or Base Case : prove that the statement holds for 0, or
1.
2. The Induction Step, Inductive Step, or Step Case: prove that
for every n, if the statement holds for n, then it holds for n+1.

Theorem 2 The hypothesis in the inductive step, that the statement holds
for a particular n, is called the induction hypothesis or inductive hy-
pothesis.

1.3 Formalization
Induction can be described in terms of quantifiers. The Axiom of Induction is
given by the following induction schema :

∀P (P (0) ∧ ∀k(P (k) −→ P (k + 1)) −→ ∀nP (n)))

3
 Any proof that uses the induction schema must show that :

1. P (0) holds.

2. P (k) −→ P (k + 1) ∀k ∈ N.

For example, let’s say we want to show that ∀n ∈ N , either n = 0 or

∃n0 , (n = n0 + 1). The base case is when we have n=0. For the inductive
step, we are given that P (n) says x = 0∨ ∃x0 , (x = x0 +1) holds, and we want
to show that P (x + 1) holds. In this case, we can do this easily by observing
that P (x + 1) expands to (x + 1) = 0∨ ∃x0 , (x + 1 = x0 + 1) we have that
x0 = x.

Excercise 1 If α > 1, then αn > 1 ∀n ∈ N.

Proof. We are given that α > 1

Base Case : We define our base case as n = 1 where n = 1 > 0, then we have
α > 1 which is true. Thus, our base case holds.
Inductive Step : Suppose the induction hypothesis holds for n, i.e. that
when n > 0 −→ αn > 1. We want to show it holds for n + 1. Since the
premise holds, we multiply both sides by a and we get an+1 = a·an > a·1 > 1.

1.4 Alternative Base Case

One of the things that is apparent in applying induction is that we are forced
to start at 0 and sometimes 0 is not the first natural number for which the
predicate holds. A generalized version of the induction schema is given
by :

(P (z 0 ) ∧ ∀z ∈ Z, z ≥ z 0 : (P (z) −→ P (z + 1))) −→ ∀z ∈ Z, z ≥ z 0 : P (z)

Excercise 2 Let n ∈ N. If n ≥ 4, then 2n ≥ n2 .

Proof. Clearly our base case is greater than 0 :

Base Case : Let n = 4 , then 2n = 24 = 16 = n2 .
Inductive Step : Assume 2n ≥ n2 . We need to show that 2n+1 ≥ (n + 1)2 =
n2 + 2n + 1. Then we can compute :

4
 2n+1 = 2 · 2n ≥ 2n2 = n2 + n2 ≥ n2 + 4n = n2 + 2n + 2n ≥ n2 + 2n + 1 =
(n + 1)2 .

1.5 Finite Series Sum

Mathematical induction can be used to validate many theorems related to
summing consecutive natural numbers. Carl Friedrich Gauss discovered the
following theorem at a very young age.

Theorem 3 The finite sum of consecutive natural numbers is given by :

n
X n(n + 1)
n = 0 + 1 + 2 + 3 + ... + n =
n=0
2
(1)

Proof.
Base Case : For n = 0 we have P (0) = 0 = 0(0+1)
2
which holds.
Inductive Step : For k ≥ 0 if P (k), then so must P (k + 1). To prove this,
we assume that the finite sum is valid up to k consecutive terms, then we
have (0+1+2+...+k)+(k +1) = k(k+1) 2
+k +1 = k(k+1)+2(k+1)
2
= (k+1)(k+2)
2
=
(k+1)(k+1+1)
2
which means P (k) holds. Hence, P (n) holds.

Excercise 3 Show that the sum of the square of consecutive natural numbers
is given by :
n
X n(n + 1)(2n + 1)
n2 = 0 + 12 + 22 + 32 + ... + n2 =
n=0
6
(2)

Proof.
0(0+1)(2(0)+1)
Base Case : For n = 0 we have P (0) = 0 = 6
which holds.

Inductive Step : For k ≥ 0 if P (k), then so must P (k + 1). To prove this,

we assume that the finite sum is valid up to k consecutive terms, then we have
2
0+12 +22 +32 +...+k 2 +(k+1)2 = k(k+1)(2k+1)
6
+(k+1)2 = k(k+1)(2k+1)+6(k+1)
6
=
k(k+1)(2k+1)+6(k+1)2 (k+1)[k(2k+1)+6(k+1)] (k+1)(2k2 +7k+1) (k+1)(k+2)(2(k+1)+1)
6
= 6
= 6
= 6
which means P (k) holds. Hence, P (n) holds.

5
Excercise 4 Show that the sum of the cubes of consecutive natural numbers
is given by :
n
X n(n + 1) 2
n3 = 0 + 13 + 23 + 33 + ... + n3 = ( )
n=0
2
(3)

Proof.
Base Case : For n = 0 we have P (0) = 0 =( 0(0+1) 2
)2 which holds.
Inductive Step : For k ≥ 0 if P (k), then so must P (k + 1). To prove this,
we assume that the finite sum is valid up to k consecutive terms, then we
2 2
have 0 + 13 + 23 + 33 + ... + k 3 + (k + 1)3 = ( k(k+1)
2
)2 + (k + 1)3 = (k+1) 4(k+2)
which means P (k) holds. Hence, P (n) holds.

Excercise 5 Show that the sum of the quadruple of consecutive natural num-
bers is given by :
n
X 6n5 + 15n4 + +10n3 − n
n4 = 0 + 14 + 24 + 34 + ... + n4 =
n=0
30
(4)

Excercise 6 Show that the sum of the quintuple of consecutive natural num-
bers is given by :
n
X n2 (n + 1)2 (2n2 + 2n − 1)
n5 = 0 + 15 + 25 + 35 + ... + n5 =
n=0
12
(5)

Excercise 7 Show that the finite sum of a gemoetric seris is given by :

n
X arn+1 − a
arn = a + ar + ar2 ... + arn =
n=0
r−1
(6)

Excercise 8 Show that every finite sequence a1 , a2 , a3 , ..., an is bounded.

6
2 Recursion
2.1 Definition
Sometimes it is possible to define an object (function, sequence, algorithm,
structure) in terms of itself. This process is called recursion. An equivalent
definition of recursion is given by :

1. 0 ∈ N.

2. If x ∈ N, then x + 1 ∈ N.

Recursion is deployed in easing calculation of complicated expressions.

Excercise 9 Consider the following recursion relation :

1. x0 = 1 ∈ N.

2. xn+1 = xxn ∈ N.

Compute 25 .

Proof.
By applying (2 ) we can break 25 into 224 and further to 2·2·2·2·2. and thus we
obtain 32.
However, when it comes to large numbers, we would need to have a better
recursive relation. One of the way to generate large numbers is with defining
power towers.

2.2 Power Towers

Theorem 4 A power tower is a chain of exponentiations which is raising
powers in a tetration sequence.

Excercise 10 Consider the following recursive formula describing the tetra-

tion of a number α copied n times :
(
1 n=0
ψ(α, n) =
αψ(α,n−1) n > 0

7
 2
22
For example, ψ(2, 4) = 22 where 2 is raised to the power of itself 4
ψ(2,3)
times so we have ψ(2, 4) = 2 = 265536 a very large number. Verify this
formula by simple induction.

Proof.
Base Case : For n = 0 we have ψ(2, 0) = 20 = 1 which holds.
Inductive Step : For k ≥ 0 if P (k), then so must P (k+1). To prove this, we
have P (k) = ψ(2, k) = 2ψ(2,k−1) then P (k + 1) = ψ(2, k + 1) = 2ψ(2,k) = 2P (k)

Excercise 11 Show that ψ(2, n) ≡ 1 (mod 5) for n ≥ 3

Proof.
22
for n = 3 we have ψ(2, 3) = 22 = 16 ≡ 1 (mod 5) and for n = 4
2
22
ψ(2, 4) = 22 = 65536 ≡ 1 (mod 5). As for all n ≥ 3 if broken down
recursively, we will end up with the first two results.

Excercise 12 Show that ψ(2, n) ≡ 0 (mod 2) for n ≥ 1

Proof. Since all power of 2 gives an even number except for n = 0 then
ψ(2, n) ≡ 0 (mod 2).

Excercise 13 Let α 6= 0 consider the following recursive functions ψ and ω

Z+ → R defined as follow :

ˆ ψ(α, 1) = ω(α, 1) = α.

ˆ ψ(α, n + 1) = αψ(α,n) and ω(α, n + 1) = ω(α, n)α .

1. Determine ψ(10, 3) and ω(10, 3).

2. Simplify ω(α, n).

3. Suppose that ψ(α, n) = αψ(α,n−1) mod 2k . Show that ψ(α, 0) = ψ(α, 2k−2 )
if k is odd.

8
2.3 Continued Fractions and Square Roots
Consider the two numbers 42 and 16. If we perform the Euclidean Division on
42
16
we would get the following :
42
16
= 2 + 13
16
We can manipulate the obtained fraction so that it becomes 161 we again per-
13
form division and obtain :
42
16
= 2 + 13
16
= 2 + 1+1 3
13
Repeating the process again and again we will end up with :
42 13
16
= 2 + 16 = 2 + 1+1 3 =2 + 1+ 1 1
13 1
4+ 3

Theorem 5 A fraction of infinite length whose denominator is a quantity

plus a fraction has the form :
Pn 1
x= = a0 +
Qn 1
a1 +
1
a2 +
a3 + · · ·
Excercise 14 Use induction to show that the numerator :

P n = an · P n-1 + P n-2 for n ≥ 2 and P 0 = a0

Excercise 15 Use induction to show that the denominator :

Qn = an · Qn-1 + Qn-2 for n ≥ 2 and Q0 = 1

Excercise 16 Consider the following infinite continued recursive fraction :
1
x=1+
1
1+
1
1+
1 + ···
Find x.
Proof.
We rewrite the infinite continued fraction as a recursive equation :
1
xn = 1 +
xn-1

9
 Since limn→+∞ xn =xn-1 , then we can say xn = xn-1 = x.Then, we solve
the equation :
1
x=1+
x
2
Which gives us a quadratic equation x − x − 1 = 0. Hence we get :
√
1+ 5
x=
2
Which is in fact called the Golden Ratio.
Theorem 6 A recursive continued square root is a nested square root that
is repeated infinitley in the form :
s r
√
q
x = n + n + n + n + ...

Excercise 17 use induction to show that :

s r
√
q
x= 6+ 6+ 6+ 6 + ... < 3

Proof.
We begin by converting the nested square root into a well defined recursive
function : √
xn = 6 + xn-1
√
Base Case : For n = 1 we have 6 < 3 which holds.
Inductvie Step : Suppose that the result is true for up to n = k then to
prove it holds for n = k + 1 we have that :
v s
u r
√ √
u q
t
xk+1 = 6 + 6 + 6 + 6 + 6 + ... = 6 + xk

Which proves the case is true of n = k + 1. Hence, by induction we have

proven the statement.
Excercise 18 use induction to show that :
s r
√
q
π
x = 2 + 2 + 2 + 2 + ... = 2cos( n+1 ), ∀n ∈ N
2
Hint : use the fact that cos2 (x) = 12 (1 + cos(2x)).

10
Excercise 19 Show that :
√
s r
√ 1
q
1+ 5
x = 1 + 1 + 1 + 1 + ... = 1 + =
1 2
1+
1
1+
1 + ···

2.4 Fibonacci Sequence

The Fibonacci numbers, commonly denoted as F n form a sequence, called the
Fibonacci sequences such that each numbers is the sum of the two proceeding
ones starting from 0 and 1.
The Fibonacci sequence is defined in the following recursive function :

ˆ F0 = 0

ˆ F 1 = 1.

ˆ F n = F n-1 + F n-2 , ∀n > 1.

Excercise 20 Using induction show that :

√
ϕn −(1−ϕ)n 1+ 5
1. Sn = √
5
;ϕ = 2
.
ϕn
2. [Sn ] = √
5
where [x] denotes the integer closest to x either up or down.

3. F n + F n+3 = F n+2 .
2
4. F2n+1 = Fn+1 + Fn 2 .
2 2
5. F2n = Fn+1 − Fn−1 .

6. Fn−1 Fn+1 − Fn2 = (−1)n ; ∀n ≥ 1 ∈ N.

7. F2n is divisible by Fn ; ∀n ∈ N.
n
8. Fn = 22 + 1.

9. Fn = F0 F1 F2 ...Fn−1 + 2 , ∀n ≥ 1 ∈ N.

10. F1 2 + F2 2 + F3 2 ... + Fn 2 = Fn Fn+1 ∀n ≥ 1 ∈ N.

11
3 Strong Induction
Strong induction is a variant of induction, in which we assume that the state-
ment holds for all values preceding n. This provides us with more information
to use when trying to prove the statement.

3.1 Definition
Now that we know how standard induction works, it’s time to look at a
variant of it, strong induction. In many ways, strong induction is similar to
normal induction. There is, however, a difference in the inductive hypothesis.
Normally, when using induction, we assume that P (n) is true to prove that
P (n + 1). In strong induction, we assume that all of P (1), P (2), ..., P (n) are
true to prove P (n + 1).

Theorem 7 A theorem is proven by strong induction if the following are

satisfied :

1. Base Case : Prove the statement holds for 0, or 1.

2. Inductive Step : Assume that P (0), P (1), P (2), .., P (n) hold and use
that to prove P (n + 1) holds.

3.2 Purpose
Why would we need to do that? Let’s go back to our domino analogy. Say
that you have infinitely many dominoes arranged in a line. But this time,
the weight of the nth domino isn’t strong enough to knock the (n + 1)th
domino.Knocking down the (n + 1)th domino requires the weight of all the
dominoes before it. Even now, if you are able to knock down the first domino,
you can prove that all the dominoes will eventually fall.

Excercise 21 Prove the Fundamental Theorem of Arithmetic using strong

induction.

Proof.
Base Case : This is clearly true for n = 2.
Inductive Step : Suppose the statement is true for n = 2, 3, 4, ..., k.. If
(k + 1) is prime, then we are done. Otherwise, (k + 1) has a smallest prime

12
factor, which we denote by p. Now let k + 1 = p × N . Since n < k, by
our inductive hypothesis, N can be written uniquely as the product of prime
numbers. That means k + 1 = p × N can also be written uniquely as a
product of primes.

Excercise 22 A chocolate bar consists of unit squares arranged in an n ×

m rectangular grid. You may split the bar into individual unit squares, by
breaking along the lines. Show that the number of breaks required is n×m−1.

Proof.
Base Case : For a 1×1 square, we are already done because we have 1−1 = 0
no breaks needed.
Inductive Step : Let P (n, m) denote the number of breaks needed to
split up an n × m square. We assume that the first break is along a row,
and we get an n1 × m and an n2 × m bar so that n1 + n2 = n. By
the induction hypothesis, the number of further breaks that we need is
n1 × m − 1 and n2 × m − 1. Hence, the total number of breaks we need
is 1 + (n1 × m − 1) + (n2 × m − 1) = (n1 + n2 ) × m − 1 = n × m − 1.

Excercise 23 Let ai be a sequence of real numbers that satisfy ai+j ≤ ai +aj ,

∀i, j. Prove that :
a1 a2 an
+ + ... ≥ an .
1 2 n

3.3 Formalization
Like simple induction, strong induction can be described in terms of quanti-
fiers. The Axiom of Induction is given by the following induction schema

∀Q(Q(0) ∧ ∀k ≤ m(Q(m) −→ Q(k + 1)) −→ ∀nQ(n)))

As with simple induction, it can be helpful to think of this approach back-

wards, by taking the contraposition. This gives the method of infinite de-
scent, due to Fermat.

Excercise 24 Show that 4n ends in either 4 or 6.

Excercise 25 Show that (2n)!! ≤ (n!)2 .

13
Excercise 26 In ancient Egypt, fractions were defined as the sum of distinct
fractions (eg. 35 = 21 + 10
1
) having their numerators as 1. A recursive algorithm
was used to calculate any fraction :

ˆ Write a fraction m
n
in the form 1
dm e
n

ˆ Calculate the fraction m

n
− 1
dm e
n

ˆ If it’s nonzero repeat the steps above

Use strong induction to prove the above recursive algorithm.

Excercise 27 Let 0 ≤ S(0) ≤ T (0), and suppose we have the following

recurrences :

S(n + 1) = αS(n) + f (n), and, T (n + 1) = βT (n) + g(n)

where 0 ≤ α ≤ β and 0 ≤ f (n) ≤ g(n) , ∀n ∈ N. Show that S(n) ≤ T (n) ,

∀n ∈ N.

Excercise 28 Consider a game called Nim. The game consists of two play-
ers having to remove n ≥ 1 matches from a box. Each player is free to remove
one, two, or three matches at a time. The player that removes the last match
loses the game. Show that by strong induction that the second player can only
win if n mod 4 = 1. Otherwise, player one wins the game.

14