Math 324 Summer 2012

Elementary Number Theory

Notes on Mathematical Induction

Principle of Mathematical Induction

Recall the following axiom for the set of integers.

Well-Ordering Axiom for the Integers

If B is a nonempty subset of Z which is bounded below, that is, there exists an n ∈ Z such that n ≤ b for
all b ∈ B, then B has a smallest element, that is, there exists a b0 ∈ B such that b0 < b for all b ∈ B, b 6= b0 .

In particular, we have

Theorem. (Well-Ordering Principle for N)

Every nonempty set of nonnegative integers has a least element.

Now we show that the Principle of Mathematical Induction and the Well-Ordering Principle for N are
logically equivalent. First we state the induction principle.

• Principle of Mathematical Induction:

If P is a set of integers such that
(i) a is in P,
(ii) for all k ≥ a, if the integer k is in P, then the integer k + 1 is also in P,
then P = {x ∈ Z | x ≥ a} that is, P is the set of all integers greater than or equal to a.

We need the following lemma which states that 1 is the smallest positive integer, and we need to be able to
prove it using either well–ordering or induction.

Lemma. 1 is the smallest positive integer.

proof.

(i) Based on the Principle of Mathematical Induction.

Let S be the set of all positive integers. We have shown that 1 ∈ S using the order properties of the
integers. If the integer k is in S, then k > 0, so that

k+1>k >0

and so the integer k + 1 is also in S. It follows from the principle of mathematical induction that S is
the set of all integers greater than or equal to 1. Therefore, 1 is the smallest positive integer.
 (ii) Based on the Well–Ordering Principle.

Suppose that 1 is not the smallest positive integer, since 1 is positive, from the Well–Ordering Principle,
there is a smallest positive integer, say s, and s < 1. If we multiply the inequality

0<s<1

by s, then
0 < s2 < s,
which implies that s is not the smallest positive integer. Because our assumption led to a contradiction,
it must be false. Therefore, 1 is the smallest positive integer.

The following lemma is true, assuming either the Well-Ordering Principle or the Principle of Mathematical
Induction.

Lemma. If n is an integer, there is no integer strictly between n and n + 1.

proof. Suppose that n is an integer and there exists an integer m such that n < m < n + 1, then p = m − n
is an integer and satisfies the inequalities 0 < p < 1, which contradicts the previous lemma. Therefore, given
an integer n, there is no integer between n and n + 1.

Theorem. The principles of mathematical induction and well–ordering are logically equivalent.

proof.

I. Assume that the well–ordering principle holds. Let a be a fixed integer, and let S be a set of integers
greater than or equal to a such that

(i) a is in S, and
(ii) for all k ≥ a, if k is in S, then k + 1 is also in S

We have to show that S is the set of all integers greater than or equal to a. Let

T = {x ∈ Z | x ≥ a and x 6∈ S},

that is, T is the set of all integers greater than or equal to a that are not in S. If T is nonempty, then it
follows from the well–ordering principle that T has a smallest element, say x0 ∈ T. Since x0 ≥ a and a 6∈ T,
then x0 > a, and since there are no integers between x0 − 1 and x0 , this implies that x0 − 1 ≥ a. Therefore,
x0 − 1 6∈ T since x0 is the smallest element of T, and so x0 − 1 must be in S. By the second property of S,
we have x0 − 1 + 1 = x0 is also in S, which is a contradicton. Because our assumption that T is nonempty
leads to a contradiction, it must be false. Therefore, T is empty and

S = {x ∈ Z | x ≥ a},

that is, S is the set of all integers greater than or equal to a, and the principle of mathematical induction
holds.
II. Assume that the principle of mathematical induction holds, assume also that there exists a nonempty set
S of integers which is bounded below by an integer a, and that S does not have a smallest element. Since
a ≤ x for every x ∈ S, and S does not have a smallest element, then a 6∈ S and therefore, a < x for all x ∈ S.

Let
T = {x ∈ Z | x ≥ a and x < s for all s ∈ S},
that is, T is the set of all integers greater than or equal to a which are strictly less than every element of S.
We have shown that a is in T. Now suppose that k ≥ a is in T, so that k < s for all s ∈ S. If k + 1 is in S,
then since there is no integer between k and k + 1, this implies that k + 1 is the smallest element of S, which
contradicts our assumption about S. Thus, if k is in T, then k + 1 must also be in T. It follows from the
principle of mathematical induction that T is the set of all integers greater than or equal to a, and so S is
empty. Therefore, if S is a nonempty set of integers which is bounded below, then S has a smallest element,
and the well–ordering principle holds.

There is a variation of the principle of mathematical induction that, in some cases, is easier to apply:

• Principle of Strong Mathematical Induction:

If P is a set of integers such that
(i) a is in P,
(ii) if all integers k, with a ≤ k ≤ n are in P, then the integer n + 1 is also in P,
then P = {x ∈ Z | x ≥ a} that is, P is the set of all integers greater than or equal to a.

Theorem. The principle of strong mathematical induction is equivalent to both the well–ordering principle
and the principle of mathematical induction.

Proof.

I. Assume that the well–ordering principle holds. Let a be a fixed integer, and let S be a set of integers such
that

(i) a is in S, and
(ii) if all integers k with a ≤ k ≤ n are in S, then n + 1 is also in S

We have to show that S is the set of all integers greater than or equal to a.

Let
T = {x ∈ Z | x ≥ a and x 6∈ S},
that is, T is the set of all integers greater than or equal to a that are not in S. If T is nonempty, then it
follows from the well–ordering principle that T has a smallest element, say x0 ∈ T. Since x0 ≥ a and a 6∈ T,
then x0 > a. Since x0 is the smallest element of T, then k ∈ S for all integers k satisfying a ≤ k ≤ x0 − 1. The
first and second properties of the set S now imply that x0 = (x0 − 1) + 1 ∈ S also, which is a contradiction.
Therefore, T is empty and
S = {x ∈ Z | x ≥ a},
that is, S is the set of all integers greater than or equal to a, and the principle of strong mathematical
induction holds.
II. Assume that the principle of strong mathematical induction holds. Let a be a fixed integer, and let S be
a set of integers such that

(i) a is in S, and
(ii) for all n ≥ a, if n is in S, then n + 1 is also in S

We show that S is the set of all integers greater than or equal to a.

From the first property of S, we know that a ∈ S. Now suppose that k ∈ S for all integers a ≤ k ≤ n, since
n ∈ S, then the second property of S implies that n + 1 ∈ S also. By the principle of strong mathematical
induction we must have
S = {x ∈ Z | x ≥ a}.
Therefore the principle of mathematical induction holds, and from the previous result the well–ordering
principle holds.

Finally, we give one version of double induction:

• Principle of Double Induction:

If P (m, n) is a doubly indexed family of statements, one for each m ≥ a and n ≥ b such that
(i) P (a, b) is true,
(ii) For all m ≥ a, if P (m, b) is true, then P (m + 1, b) is true,
(iii) For all n ≥ b, if P (m, n) is true for all m ≥ a, then P (m, n + 1) is true for all m ≥ a,
then P (m, n) is true for all m ≥ a and n ≥ b.

The proof follows immediately from the usual statement of the principle of mathematical induction and is
left as an exercise.

Examples Using Mathematical Induction

We now give some classical examples that use the principle of mathematical induction.

Example 1. Given a positive integer n, consider a square of side n made up of n2 1 × 1 squares. We will
show that the total number Sn of squares present is
n
X n(n + 1)(2n + 1)
Sn = k2 = . (∗)
6
k=1

Solution. For example, if n = 4, then it is easily seen from the figure

that the total number of squares present is 30, since there are

42 = 16 1 × 1 squares
2
3 =9 2 × 2 squares
2
2 =4 3 × 3 squares
2
1 =1 4 × 4 squares

for a total of 30.

We will show that (∗) is true by induction on n.

Base Case: For n = 1, there is only 1 square, so that S1 = 1, and

1
X
k 2 = 12 = 1,
k=1

so that (∗) is true for n = 1.

Inductive Step: Let n ≥ 1 be arbitrary and assume that (∗) is true for n. Consider an (n + 1) × (n + 1)
square, where we have added 2n + 1 unit squares along the bottom and right hand side of an n × n square,
as shown in the figure.

The only new squares that have been added are those that contain one of the new unit squares on the border,
and we can count these as follows.

For each k with 1 ≤ k ≤ n + 1, we have

2[n + 1 − (k − 1)] − 1 = 2(n + 2 − k) − 1

squares of side k,

n+1−k

k
and therefore we have added
n+1
X n+1
X
[2(n + 2 − k) − 1] = 2 (n + 2 − k) − (n + 1)
k=1 k=1
n+1
X
=2 k − (n + 1)
k=1
= (n + 1)(n + 2) − (n + 1)
= (n + 1)2

new squares.

From the inductive hypothesis, we have

n
X n+1
X
2 2 2
Sn+1 = Sn + (n + 1) = k + (n + 1) = k2
k=1 k=1

n
k 2 for all n ≥ 1.
P
Therefore, by the Principle of Mathematical Induction, we have Sn =
k=1

Example 2. Let a1 , a2 , . . . , an be positive real numbers. The arithmetic mean of these numbers is defined
by
a1 + a 2 + · · · + a n
A= ,
n
and the geometric mean of these numbers is defined by
1
G = (a1 · a2 · · · an ) n .

The Arithmetic-Geometric Mean Inequality states that:

G≤A (∗)

and equality holds if and only if a1 = a2 = · · · = an .

Proof. We will give a proof of (∗) by induction on n. We note first that if we are given any positive real
numbers
a1 , a2 , . . . , an ,
we may assume, by relabelling if necessary, that

a1 ≤ a 2 ≤ · · · ≤ a n .

If this is the case, then clearly

na1 ≤ a1 + a2 + · · · + an ≤ nan ,
so that a1 ≤ A ≤ an , and A − a1 ≥ 0 and an − A ≥ 0. Therefore,

(A − a1 )(an − A) = Aan + Aa1 − A2 − a1 an ≥ 0,

that is,

A(a1 + an − A) ≥ a1 an . (∗∗)
Base Case: If n = 1, then
a1
A= = (a1 )1 = G,
1
and (∗) is true for n = 1.

Inductive Step: Let n be an arbitrary positive integer with n ≥ 2, and suppose that (∗) is true for any set of
n − 1 positive real numbers. Let a1 , a2 , . . . , an be a set of n positive real numbers, let A be their arithmetic
mean and let G be their geometric mean. We may assume without loss of generality that

a1 ≤ a 2 ≤ · · · ≤ a n .

Now consider the set of n − 1 positive real numbers

a2 , a3 , . . . , an−1 , (a1 + an − A),

the arithmetic mean of these n − 1 numbers is

a2 + a3 + · · · + an−1 + (a1 + an − A) (a1 + a2 + · · · + an ) − A
=
n−1 n−1
nA − A
=
n−1
= A,

that is, they have the same arithmetic mean as the original n integers.

By the inductive hypothesis,

1
A ≥ a2 · a3 · · · an−1 (a1 + an − A) n−1 ,

so that
An−1 ≥ a2 · a3 · · · an−1 (a1 + an − A).
Muliplying this last inequality by A, we have from (∗∗),

An ≥ a2 · a3 · · · an−1 A(a1 + an − A) ≥ a2 · a3 · · · an−1 · a1 · an = Gn ,

so that G ≤ A, that is, (∗) is also true for n. This completes the proof of the inequality by induction.

We leave it as an exercise to show that equality holds if and only if a1 = a2 = · · · = an using the principle of
mathematical induction. We give an alternate proof due to Besicovitch which uses the following fact (easily
proven using calculus):

Lemma. For all real numbers x,

ex ≥ 1 + x
with equality if and only if x = 0.

Alternate Proof. Besicovitch’s proof is very simple. Let a1 , a2 , . . . , an be n positive real numbers, and let
A be their arithmetic mean, from the lemma, the following inequalities hold
ak
e(ak /A−1) ≥ for k = 1, 2, . . . , n.
A
Multiplying these inequalities together, we have
n
Y a1 · a2 · · · an
1 = e0 = e(ak /A−1) ≥ ,
An
k=1

so that An ≥ a1 · a2 · · · an , and taking the nth root, we have A ≥ G with equality if and only if ak = A for
all k = 1, 2, . . . , n.

Example 3. For any positive integer n > 2, we have

n   n−1
2n − 2

Y n
< .
k n−1
k=0

Proof. We apply the Arithmetic-Geometric Mean Inequality to the n − 1 positive real numbers
       
n n n n
, , , ...,
1 2 3 n−1

to obtain
1
n−1
Y ! n−1 n−1
X  n 2 n − 2
n 1
< · = ,
k n−1 k n−1
k=1 k=1
   
n n
and since = = 1, then
0 n
n   n−1
2n − 2

Y n
< .
k n−1
k=0

Example 4.

(a) Let {an }n≥0 , be the unique solution to the discrete initial value problem

an+2 = an+1 + an n≥0

a0 = 0
a1 = 1,

that is, an is the nth term in the Fibonacci sequence, then

" √ !n √ !n #
1 1+ 5 1− 5
an = √ −
5 2 2

for all n ≥ 0. This is called Binet’s formula, it was first discovered by DeMoivre, and later independently
by Binet.
√
1+ 5 αn
(b) Let α = , then an is the nearest integer to √ for all n ≥ 0.
2 5
Solution: We prove Binet’s formula using the principle of mathematical induction later, here we solve the
discrete initial value problem.

(a) Assuming a solution of the form an = λn , the characteristic equation becomes λ2 = λ + 1, with two
distinct real roots, √ √
1+ 5 1− 5
λ1 = and λ2 = ,
2 2
so the general solution is
√ !n √ !n
1+ 5 1− 5
an = A · +B· ,
2 2
where the constants A and B are determined from the initial conditions
√ ! √ !
1+ 5 1− 5
a0 = A + B = 0 and a1 = A · +B· =1
2 2

to be
1 1
A= √ and B = −√ ,
5 5
so that " √ !n √ !n #
1 1+ 5 1− 5
an = √ −
5 2 2
for all n ≥ 0.

1 1
(b) Since √ < , then
5 2
√ !n
1 1− 5 1
√ < ,
5 2 2
so that √ !n
1 1 1− 5 1
− < −√ <
2 5 2 2
√ !n √ !n
1 1+ 5 1 1 1+ 5 1
and therefore, from Binet’s formula, √ − < an < √ + . Equivalently,
5 2 2 5 2 2
√ !n √ !n
1 1+ 5 1 1 1+ 5
an − √ < so that an is the nearest integer to √ .
5 2 2 5 2

Example 5. Let {an }n≥0 be a sequence of real numbers satisfying the recurrence relation and initial
conditions below.

an = an−1 + 2an−2 + 3an−3 + · · · + na0 + 1, n≥1

a0 = 1.

(a) Compute the next 5 terms of the sequence, that is, compute a1 , a2 , a3 , a4 , a5 .
(b) From part (a), make a conjecture as to the value of an for any positive integer n.
(c) Use the principle of mathematical induction to prove that your conjecture in part (b) is correct.
Solution:

(a) From the recurrence relation and the initial conditions we have
a0 = 1
a1 = 1 · a 0 + 1 = 1 · 1 + 1 = 2
a2 = a 1 + 2 · a 0 + 1 = 2 + 2 · 1 + 1 = 5
a3 = a2 + 2 · a1 + 3 · a0 + 1 = 5 + 2 · 2 + 3 · 1 + 1 = 13
a4 = a3 + 2 · a2 + 3 · a1 + 4 · a0 + 1 = 13 + 2 · 5 + 3 · 2 + 4 · 1 + 1 = 34
a5 = a4 + 2 · a3 + 3 · a2 + 4 · a1 + 5 · a0 + 1 = 34 + 2 · 13 + 3 · 5 + 4 · 2 + 5 · 1 + 1 = 89

(b) It appears that for all n ≥ 0, we have an = F2n+1 , that is, the Fibonacci numbers with odd indices.
(c) We will show that the sequence {an }n≥0 satisfies the same recurrence relation and initial conditions as
the sequence {F2n+1 }n≥0 , and then an easy inductive argument shows that an = F2n+1 for all n ≥ 0.
First we note that for n ≥ 1, we have
F2n+3 = F2n+2 + F2n+1 = (F2n+1 + F2n ) + F2n+1 = 2F2n+1 + F2n
= 2F2n+1 + (F2n+1 − F2n−1 ) = 3F2n+1 − F2n−1 ,
and the sequence {F2n+1 }n≥0 satisfies the discrete initial value problem
F2n+3 = 3F2n+1 − F2n−1 , n ≥ 1
F1 = 1
F3 = 2.

For the sequence {an }n≥0 , we have

an+1 = 1 · an + 2 · an−1 + 3 · an−2 + · · · + (n − 1) · a2 + n · a1 + (n + 1) · a0 + 1
an = 1 · an−1 + 2 · an−2 + 3 · an−3 + · · · + (n − 1) · a1 + n · a0 + 1
and subtracting the second equality from the first, we have
an+1 − an = an + an−1 + · · · + a2 + a1 + a0 ,
that is,
n
X
an+1 − an = ak . (∗)
k=0

Therefore,
n−1
X
an+1 − 2an = ak
k=0
for all n ≥ 1.
However, from (∗) with n replaced by n − 1, we get
n−1
X
an+1 − 2an = ak = an − an−1 ,
k=0

and therefore,
an+1 = 3an − an−1 , n ≥ 1
a0 = 1
a1 = 2,
 and the sequence {an }n≥0 satisfies exactly the same discrete initial value problem as {F2n+1 }n≥0 .
To see that this implies that an = F2n+1 for all n ≥ 0, we define

bn = an − F2n+1

for n ≥ 0, and note that the sequence {bn }n≥0 satisfies

bn+1 = 3bn − bn−1 , n ≥ 1

b0 = 0
b1 = 0,

and now an easy inductive argument shows that bn = 0 for all n ≥ 0.

Example 6. Let a be a positive real number such that

1
a+
a
is an integer. Use the principle of strong mathematical induction to show that
1
an + (∗)
an
is also an integer for all positive integers n.

Solution: Let a be a positive real number such that

1
a+
a
is an integer.

Base Case: We will show that (∗) is also true for n = 2. We have
 2
1 1 1 1
a+ = a2 + a · + 2 = a2 + 2 + 1,
a a a a
so that  2
2 1 1
a + 2 = a+ − 1.
a a

Since the expression on the right side of this equality is an integer, then the expression on the left side is
also an integer.

Inductive Step: Assume that (∗) is true for all integers k such that 1 ≤ k ≤ n, we will show that this implies
that (∗) is also true for n + 1. We have
  
1 1 1 1 1 1 1
an + n a+ = an+1 + an · + a · n + n+1 = an+1 + n+1 + an−1 + n−1
a a a a a a a
so that     
n+1 1 n 1 1 n−1 1
a + = a + n a+ − a + .
an+1 a a an−1
From the inductive hypothesis, the expression on the right side of this equality is an integer, so that the
expression on the left side is also an integer, and (∗) is true for n + 1.

By the principle of strong mathematical induction the result is true for all positive integers n.
Example 7. Let an be the number of strings of length n from the alphabet Σ = { 0, 1, 2 } with no
consecutive 0’s.

(a) Find a1 , a2 , a3 , a4 .
(b) Give a simple counting argument to show that

an = 2an−1 + 2an−2

for all n ≥ 3.
(c) Use the principle of strong mathematical induction to show that
√ n+2  √ n+2
 
1 
an = √ 1+ 3 − 1− 3
4 3
for all n ≥ 0.

Solution:

(a) For n = 1, every string of length 1 from the alphabet Σ = { 0, 1, 2 } contains no consecutive 0’s, and
therefore a1 = 3.
For n = 2, the total number of strings of length 2 is 32 , and there is only one string with consecutive
0’s, namely 0 0, and therefore, a2 = 32 − 1 = 8.
For n = 3, there are only 5 strings of length 3 that contain consecutive 0’s, namely,

0 0 0 1 0 0 2 0 0 0 0 1 0 0 2,

and the total number of strings of length 3 from the alphabet Σ = { 0, 1, 2 } is 33 , and therefore
a3 = 33 − 5 = 22.
For n = 4, given a string of length 4 from the alphabet Σ = { 0, 1, 2 } with no consecutive 0’s, it either
starts with a 0, a 1, or a 2.
If it starts with a 0, the second element of the string must be either a 1 or a 2, and so there are
2a2 strings of length 4 with no consecutive 0’s that start with a 0.
If it starts with a 1, then there are a3 strings of length 4 with no consecutive 0’s that start with
a 1.
If it starts with a 2, then there are a3 strings of length 4 with no consecutive 0’s that start with
a 2.

Since this accounts for all strings of length 4 with no consecutive 0’s, and since these cases are mutually
exclusive, then
a4 = 2a2 + 2a3 = 2 · 8 + 2 · 22 = 60.

(b) We can use the method we used to determine a4 to find a recurrence relation satisfied by an for all
n ≥ 3. Any string of length n with no consecutive 0’s from the alphabet Σ = { 0, 1, 2 } either starts
with a 0, a 1, or a 2. Reasoning as above, there are 2an−2 that start with a 0, an−1 that start with a
1, and an−1 that start with a 2. This accounts for all such strings of length n, and therefore

an = 2an−1 + 2an−2

for all n ≥ 3.
(c) If we want the formula (∗) below to hold for all n ≥ 0, we need to define a0 , and we do this using the
recurrence relation and the values of a1 and a2 . We want

8 = a2 = 2a1 + 2a0 = 6 + 2a0 ,

so that we should define a0 = 1. This makes sense, since there is only one string of length 0, namely,
the empty string, and it has no consecutive 0’s.

Now the recurrence relation

an+2 = 2an+1 + 2an
holds for all n ≥ 0, and we will use this to show by the principle of strong mathematical induction that
√ n+2  √ n+2
 
1 
an = √ 1+ 3 − 1− 3 (∗)
4 3
is true for all n ≥ 0.
Base Case: For n = 0, we have
√ 2  √ 2 √ √ i
 
1  1 h 
√ 1+ 3 − 1− 3 = √ 4 + 2 3 − 4 − 2 3 = 1 = a0
4 3 4 3
and (∗) holds for n = 0.
Inductive Step: Let n ≥ 0 be arbitrary and assume that (∗) holds for all integers k with 0 ≤ k ≤ n,
then from the recurrence relation we have

an+1 = 2an + 2an−1

√ n+2  √ n+2 √ n+1  √ n+1
   
1  1 
= √ 1+ 3 − 1− 3 + √ 1+ 3 − 1− 3
2 3 2 3

√ n+2  √ n+1 √ n+2  √ n+1

   
1  1 
= √ 1+ 3 + 1+ 3 − √ 1− 3 + 1− 3
2 3 2 3

√  √ n+1 √  √ n+1
   
1  1 
= √ 2+ 3 1+ 3 − √ 2− 3 1− 3
2 3 2 3

" √ # " √ #
1 (1 + 3)2  √ n+1 1 (1 − 3)2  √ n+1
= √ 1+ 3 − √ 1− 3 ,
2 3 2 2 3 2

since √ 2 √ √ √
(1 + 3) = 2(2 + 3) and (1 − 3)2 = 2(2 − 3).
Therefore,
√ n+3  √ n+3
 
1 
an+1 = √ 1+ 3 − 1− 3 ,
4 3
and (∗) also holds for n + 1.
Therefore, (∗) holds for all integers n ≥ 0 by the principle of strong mathematical induction.
Example 8. Let an , n ≥ 1, be the solution to the problem
n
an+1 = 1 + , n≥1
an
a1 = 1.

Show that √ √
n ≤ an ≤ n+1
for n ≥ 1, and the inequalities are strict for all integers n > 1.

√ √
Solution: We will prove that n ≤ an ≤ n + 1 for n ≥ 1 by induction on n. If n = 1, then
√ √
1 = 1 = a1 ≤ 2 = 1 + 1

and the result is true for n = 1. Now suppose the result is true for some n ≥ 1, then
√ n √
an+1 − n+1=1+ − n+1
an
n √

= − n+1−1
an
n n
= −√
an n+1+1
√

n n + 1 + 1 − an
= √

an n+1+1
√ √

n n+1− n
≥ √

an n+1+1
>0
√
from the induction hypothesis, that is, an+1 > n + 1. Also,
√ √ n
n + 1 + 1 − an+1 = n + 1 −
an
√ n
≥ n+1− √
n
√ √
= n+1− n
>0
√
from the induction hypothesis, that is, an+1 < n + 1 + 1. Thus,
√ √
n + 1 < an+1 < n + 1 + 1,

so we have shown that if the result is true for some n ≥ 1, this implies that it is true for n+1 also. Therefore,
by the principle of mathematical induction, the result is true for all n ≥ 1.
Example 9. If Fn is the nth Fibonacci number, then
√
Fn+1 1+ 5
lim = .
n→∞ Fn 2

Solution. Recall that the Fibonacci sequence {Fn }n≥0 is the unique solution to the discrete initial value
problem

Fn+2 = Fn+1 + Fn , n≥0

F0 = 0
F1 = 1.

The first few terms of the sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .

We proved Cassini’s Identity:

Fn+1 Fn−1 − Fn2 = (−1)n
for all integers n ≥ 1, by evaluating the determinant of the matrix
 
n Fn+1 Fn
A = ,
Fn Fn−1
 
1 1
where A = , in two different ways.
1 0

Here we will use Cassini’s identity to show that the sequence

 
Fn
γn =
Fn+1 n≥1
√
5−1
converges and that lim γn = .
n→∞ 2
After examining the terms
F2n F2n−2
− ,
F2n+1 F2n−1
it appears that they are all positive, and that F2n · F2n−1 − F2n+1 · F2n−2 = 1 for all n ≥ 1. For example, if
n = 1, we have
F2 · F1 − F3 · F0 = 1 · 1 − 2 · 0 = 1.

Lemma 1. For each n ≥ 1,

F2n · F2n−1 − F2n+1 · F2n−2 = 1, (∗)

so that
F2n−2 F2n
0 < γ2n−2 = < = γ2n < 1
F2n−1 F2n+1
for all n ≥ 2. Therefore the sequence {γ2n }n≥1 is strictly increasing and bounded above, hence converges.
proof. If n ≥ 1, then
   
F2n · F2n−1 − F2n+1 · F2n−2 = F2n−1 + F2n−2 · F2n−1 − F2n + F2n−1 · F2n−2
2
= F2n−1 + F2n−2 · F2n−1 − F2n · F2n−2 − F2n−1 · F2n−2
2
= F2n−1 − F2n · F2n−2
= −(−1)2n−1
=1

by Cassini’s identity. Therefore, (∗) is true for all n ≥ 1.

After examining the terms

F2n−1 F2n+1
− ,
F2n F2n+2
it appears that they are all positive, and that F2n+2 · F2n−1 − F2n · F2n+1 = 1 for all n ≥ 1. For example, if
n = 1, we have
F4 · F1 − F2 · F3 = 3 · 1 − 1 · 2 = 1.

Lemma 2. For each n ≥ 1,

F2n+2 · F2n−1 − F2n · F2n+1 = 1, (∗∗)

so that
F2n+1 F2n−1
0 < γ2n+1 = < = γ2n−1 < 1
F2n+2 F2n
for all n ≥ 2. Therefore the sequence {γ2n−1 }n≥1 is strictly decreasing and bounded below, hence converges.

proof. If n = 1, then
   
F2n+2 · F2n−1 − F2n · F2n+1 = F2n+1 + F2n · F2n−1 − F2n · F2n + F2n−1
2
= F2n+1 · F2n−1 + F2n · F2n−1 − F2n − F2n F2n−1
2
= F2n+1 · F2n−1 − F2n
= (−1)2n
=1

by Cassini’s identity. Therefore, (∗∗) is true for all n ≥ 1.

Now let
u = lim γ2n and v = lim γ2n+1 ,
n→∞ n→∞
then from Cassini’s identity, we have
2
F2n+1 · F2n−1 − F2n = (−1)2n = 1,

so that
F2n−1 F2n (−1)2n
γ2n−1 − γ2n = − = ,
F2n F2n+1 F2n · F2n+1
and letting n → ∞, we have v − u = 0, that is, u = v.
Now, given  > 0, there exists an integer N1 such that |u − γ2n | <  for all positive integers n such that
2n > N1 , and there exists an integer N2 such that |v − γ2n+1 | <  for all positive integers n such that
2n + 1 > N2 . Let N = max{N1 , N2 }, since u = v, we have |u − γn | <  for all n > N. So we have shown that
given any  > 0, there exists an integer N such that |u − γn | <  whenever n > N, but this is exactly what
we mean when we say lim γn = u.
n→∞

Now we know that the limit u = lim γn exists, but we still don’t know its value. If we look at the difference
n→∞
equation for the Fibonacci numbers, Fn+2 = Fn+1 + Fn , and divide both sides by Fn+1 , then we have
Fn+2 Fn
=1+
Fn+1 Fn+1
for all n ≥ 1, that is,
1 Fn
=1+
Fn+1 Fn+1
Fn+2
for all n ≥ 1, and letting n → ∞, we get
1
= 1 + u.
u
Therefore, u satisfies the quadratic equation u2 + u − 1 = 0, with distinct real roots
√ √
−1 + 5 −1 − 5
λ1 = and λ2 = .
2 2
Since each term in the sequence satisfies 0 < γn < 1, then the limit is the positive root
√
5−1
u = lim γn = .
n→∞ 2
It follows from this that √
Fn+1 1+ 5
lim =
n→∞ Fn 2
the Golden Ratio.

Example 10. For any m ≥ 1 and n ≥ 1, we have

(m + 1)n > mn.

Solution: The proof is by double induction. For each m ≥ 1 and n ≥ 1, let P (m, n) be the statement that
(m + 1)n > mn.

For m = 1 and n = 1, the statement P (1, 1) is just the inequality

(1 + 1)1 > 1 · 1,

that is 2 > 1, which is true.

Now suppose that m ≥ 1, and P (m, 1) is true, then

1
(m + 1) + 1 = m + 2 > m + 1 = (m + 1) · 1,

so that P (m + 1, 1) is true also.

Finally, let n ≥ 1, and suppose that P (m, n) is true for all m ≥ 1, then

(m + 1)n+1 = (m + 1)(m + 1)n > (m + 1)(mn) ≥ mn + m = m(n + 1),

since m ≥ 1 and n ≥ 1 imply that m2 n + mn ≥ mn + m. Therefore, P (m, n + 1) is true for all m ≥ 1.

Thus, we have shown that

(i) P (1, 1) is true,

(ii) For all m ≥ 1, if P (m, 1) is true, then P (m + 1, 1) is true,
(iii) For all n ≥ 1, if P (m, n) is true for all m ≥ 1, then P (m, n + 1) is true for all m ≥ 1,

and by the principle of double induction, P (m, n) is true for all m ≥ 1 and n ≥ 1.

Inductive and Recursive Definitions

Definition. A function f : Z+ → R is said to be defined inductively if and only if

(i) f (1) is given,

(ii) f (n + 1) is given in terms of f (n), or even in terms of all f (k), for k = 1, 2, . . . , n.

Examples of functions that are defined inductively are given below.

Example 11. The factorial function

f (n) = n!
for n ≥ 1, is defined inductively by

f (1) = 1

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

Example 12. The power function

f (n) = 2n
for n ≥ 0, is defined inductively by

f (0) = 1,

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

Definition. A function f :→ R is said to be defined recursively if and only if each value f (n) is either

(i) given explicitly, or

(ii) given in terms of previously defined values of f.
Examples of recursively defined functions are given below.

Example 13. The Fibonacci sequence {fn }n≥0 given by

f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 ···
0 1 1 2 3 5 8 13 21 34 55 89 144 ···
is defined recursively by
f0 = 0

f1 = 1

fn+2 = fn+1 + fn , n ≥ 0.
We can give an explicit formula for the terms in the Fibonacci sequence:
" √ !n √ !n #
1 1+ 5 1− 5
fn = √ −
5 2 2
for n ≥ 0, namely, Binet’s formula.

We will prove this using strong induction (earlier we gave a proof by solving a discrete initial value problem).
Let √ √
1+ 5 1− 5
α= and β= ,
2 2
then α2 = α + 1 and β 2 = β + 1. We will show that
1
fn = √ [αn − β n ] (∗)
5
for all integers n ≥ 0.

Base Case: n = 0 :
1  1
√ α0 − β 0 = √ [1 − 1] = 0,

5 5
and f0 = 0, so that (∗) holds for n = 0.

Inductive Step: Assume that (∗) is true for all integers k with 0 ≤ k ≤ n + 1, we will show that this implies
that (∗) is true for n + 2. Let
1
am = √ [αm − β m ]
5
for m ≥ 0, then we have
1 
an+2 = √ αn+2 − β n+2

5
1 
= √ αn α2 − β n β 2

5
1
= √ [(α + 1)αn − (β + 1)β n ]
5
1  1
= √ αn+1 − β n+1 + √ [αn − β n ]

5 5
= fn+1 + fn
from the inductive hypothesis. Thus,
1 
√ αn+2 − β n+2 = fn+1 + fn = fn+2 ,

5
and (∗) is true for n + 2. By the principle of mathematical induction, (∗) is true for all integers n ≥ 0.
  
n
Example 14. The binomial coefficients given by
k
n!

for 0 ≤ k ≤ n,
  
n
= k!(n − k)!
k
0 otherwise


for n ≥ 0, are defined recursively by

 
n
= 1, n ≥ 0,
0
 
0
= 0, k ≥ 1,
k
     
n n−1 n−1
= + , 1 ≤ k ≤ n.
k k k−1

Note: Recursive definitions are more general than inductive definitions in that the value of f (n) may be
defined using previous values of f (k) with k > n.

Inductive definitions have the important advantage that it is easy to verify that they really are definitions.
Recursive definitions often require special arguments to verify that f (n) is indeed defined for all positive
integers n.

Example 15. A recursive definition that is not an inductive definition.

For n ≥ 1, define 
 1 if n is a multiple of 3,
f (n) =
 1 + f (n + 1) if n is not a multiple of 3.

Note that from the first part of the recursive definition, we have
f (3) = f (6) = f (9) = f (12) = f (15) = · · · = 1.

Now we compute
f (1) = 1 + f (2)
and
f (2) = 1 + f (3) = 1 + 1 = 2,
so that
f (1) = 1 + 2 = 3.

Continuing,
f (4) = 1 + f (5) = 1 + 1 + f (6) = 1 + 1 + 1 = 3,

f (7) = 1 + f (8) = 1 + 1 + f (9) = 1 + 1 + 1 = 3,

f (8) = 1 + f (9) = 1 + 1 = 2,

..
.
and it is easy to see, since for any three consecutive integers, one of them has to be a multiple of 3, that the
computation of f (n) always terminates after using at most two other values of n. Thus, the function f is in
fact defined for all n ≥ 1.

In fact, we can define f nonrecursively as



 1 for n ≡ 0 (mod 3)



f (n) = 3 for n ≡ 1 (mod 3)


2 for n ≡ 2 (mod 3)



for n ≥ 1.