Section 004) Principle of Mathematical Induction

Introduction 

Principle of Mathematical induction (in short also known as PMI) is a method for proving a
proposition.  This consists of 2 steps the $1^{st}$ step is called the base case (also called basis)
and the $2^{nd}$ step is called induction step.

To prove by mathematical induction we have a hypothesis and then prove the hypothesis. The hypothesis is called induction hypothesis.They are explained below.

Steps  In Principle of Mathematical Induction 

In PMI the 2 steps are
Base step: This is true for some starting value say n. Typically but not always n = 1.
Induction step: Say this is true for all $n <=k$. Then it is true for k+ 1.
Combining the above 2 we prove it by mathematical induction.

There are two principles of mathematical induction

1st Principle of Mathematical Induction

In case the inductive step is based on the last value only then it is the 1st  Principle of
Mathematical Induction.

2nd Principle of Mathematical Induction

If it is based on more than one value then this is called 2nd Principle of Mathematical Induction.
This is also known as Principle of Strong Mathematical Induction as it is based on k and k-1 (or more than one value).

Proof  by Principle of Mathematical Induction

To prove by Principle of Mathematical Induction both the steps need to be proved. In absence of any one the proof is incomplete and hence is invalid.

This is demonstrated below how the proof by induction can be wrong unless applied properly.

To illustrate this, Joel E. Cohen proposed the following argument, which purports to prove by
mathematical induction that all horses are of the same color.

Base case: In a set of only one horse, there is only one color.

Inductive step: Assume as induction hypothesis that within any set of n horses, there is only
one color. Now look at any set of n + 1 horses. Number them: 1, 2, 3, ..., n, n + 1. Consider
the sets {1, 2, 3, ..., n} and {2, 3, 4, ..., n + 1}. Each is a set of only n horses, therefore
within each there is only one color. But the two sets overlap, so there must be only one color
among all n + 1 horses.

The base case n = 1 is trivial (as any horse is the same color as itself), and the inductive step
is correct in all cases $n > 1$. However, the logic of the inductive step is incorrect for n = 1,
Because the statement that "the two sets overlap" is false (there are only n + 1 = 2 horses prior
to either removal, and after removal the sets of one horse each do not overlap).

Hence the principle of induction has not been applied correctly and hence incorrect conclusion.

Here we provide couple of examples

Problem 1

Using PMI prove that $x^2+3x+3$ is a factor of $(x+1)^{n+1} + (x+2)^{2n-1}$
for integer $n >= 1$

Solution 1

n =1 gives $(x+1)^{n+1} + (x+2)^{2n-1} = (x+1)^2 + (x+2) = x^2 + 2x + 1 + x + 2 = x^2 + 3x + 3$ divisible

So the 1st step that is base step is proved

Let it be true for n = k.

We need to prove for n= k+ 1
Let $f(k) = (x+1)^{k+1} + (x+ 2)^{2k- 1}$
So $f(k+1) = (x+1)^{k+2} + (x+2)^{2k+ 1}$
$= (x+1)(x+1)^k + (x+2)^2 *(x+2)^{2k-1}$
$= (x+1)(x+1)^k + (x^2+4x + 4) *(x+2)^{2k-1}$
$= (x+1)(x+1)^k + (x + 1 + x^2+3x + 3) *(x+2)^{2k-1}$
$= (x+1)(x+1)^k + (x + 1)(x+2)^{(2k-1} + (x^2+3x + 3) *(x+2)^{2k-1}$
$= (x+1)[(x+1)^k + (x+2)^{2k-1}] + (x^2+3x + 3) *(x+2)^{2k-1}$
$= (x+1) f(k) + (x^2+3x + 3) *(x+2)^{2k-1}$

As both terms are divisible by $x^2+3x+3$ so f(k+1) is divisible by $x^2+3x+3$

So step of induction is proved

Hence proved as we have proved both the base step and induction step to be true.

Problem 2

Suppose x is a real number  and $x + \frac{1}{x}$ is an integer
Prove for all $n > 1, x^n + \frac{1}{x^n}$ is an integer.

Solution 2

$x+ \frac{1}{x} = n$ Say n integer (given)
So $(x+ \frac{1}{x})^2 = n^2$
$x^2 + \frac{1}{x^2} = n^2-2$ is an integer
So true for 1 and true for 2
Let it be true for upto k
Now $x^k+ \frac{1}{x^k}$
$(x^k+ \frac{1}{x^k})(x+ \frac{1}{x})$
$= (x^{k+1} + \frac{1}{x^{k-1}}) + x^{k-1} + \frac{1}{x^{k+1}}$
So $(x^{k+1} + \frac{1}{x^{k+ 1}})= (x^k+ \frac{1}{x^k})(x+ \frac{1}{x})- (x^{k-1} + \frac{1}{x^{k-1}})$
If it is true for all n upto k so RHS is integer then LHS is integer so for n = k+ 1 it is an ingeger so the
induction step is proved
Hence proved