MATH 122
MATHEMATICAL INDUCTION

Let P_n be a statement involving the positive integer n.

Examples:

1. n² = n × n
2. 2n is an even number
3. 2n + 1 is an odd number
4. $\frac{n+1}{n}=1$
5. n is divisible by 3
6. $1+2+3+\cdots +n=\frac{n\left(n+1\right)}{2}$

Which of the above statements are true for ALL positive integral values of n?

Answer: a, b, c and f (f is not obviously true)
Note that d is not true for any value of n, while e is only true for
n = 3, 6, 9, ...

f is true for the following reason:

$\underset{=n+1}{\underbracket{1+\underset{=n+1}{\underbracket{2+\underset{=n+1}{\underbracket{3+\cdots +\left(n-2\right)}}+\left(n-1\right)}}+n}}$ = sum of the first n terms of this arithmetic series (S_n).

Thus $S_n=\frac{n}{2}\left(a_1+a_n\right)=\frac{n}{2}\left(1+n\right)=\frac{n\left(n+1\right)}{2}$

Notation:

If P_n is a statement,
Then P₁ is this statement where n = 1
P₂ is this statement where n = 2, etc.

Example:

Let P_n be: n² + n is positive.
Then P₁ says, "1² + 1 is positive",
P₄ says, "4² + 4 is positive", etc.

AXIOM OF MATHEMATICAL INDUCTION

Let P_n be a statement (i.e.P₁, P₂, P₃, ... etc. are defined).

Furthermore, let the following 2 conditions exist:

1. P₁ is true
2. P_k+1 is true whenever P_k is true. (k is any positive integer.)

Conclusion: P_n is true for n = 1, 2, 3, ...

i.e. P₁, P₂, P₃, P₄,... are all true.

 

---

EXAMPLE 1:

PROVE   $1+2+3+\cdots +n=\frac{n\left(n+1\right)}{2}$ by mathematical induction. (i.e. Prove that P_n is true for n = 1, 2, 3, ...)

P_n: $1+2+3+\cdots +n=\frac{n\left(n+1\right)}{2}$

P₁: $1=\frac{1\left(1+1\right)}{2}$, i.e., 1 = 1   SO   P₁ is true.

ASSUME P_k is true: i.e., $1+2+3+\cdots +k=\frac{k\left(k+1\right)}{2}$
PROVE P_k+1 is true: i.e., Prove $1+2+3+\cdots +\left(k+1\right)=\frac{\left(k+1\right)\left(k+2\right)}{2}$

USUALLY YOU START ALL WITH THE LEFT SIDE OF P_k+1:

$\begin{array}{l}1+2+3+\cdots +\left(k+1\right)=\\ \underset{\text{left side of }{P}_k}{\underbrace{1+2+3+\cdots +k}}+\left(k+1\right)=\\ \Updownarrow \\ \frac{\stackrel{\text{right side of }{P}_k}{\overbrace{k\left(k+1\right)}}}{2}+\left(k+1\right)=\\ \frac{k\left(k+1\right)+2\left(k+1\right)}{2}=\text{ right side of }{P}_{k+1}\end{array}$
Therefore, P_n true for n = 1, 2, 3,...

---

EXAMPLE 2

SHOW THAT: P_n: 5ⁿ - 1 is divisible by 4.

P₁:   $\frac{5^1-1}{4}=\frac{5-1}{4}=\frac{4}{4}=1$   Therefore: P₁ is true.

ASSUME P_k:   5^k − 1 divisible by 4.
or $\frac{5^k-1}{4}=q$ , is an integer
Then 5^k − 1 = 4q and 5^k = 4q + 1
PROVE P_k+1: 5^k+1 - 1 divisible by 4.

$\begin{array}{c}{5}^{k+1}-1=\\ 5^k·5-1=\\ \stackrel{\text{replaces }{5}^k}{\overbrace{\left(4q+1\right)}}·5-1=4q·5+1·5-1\\ =\underset{\text{divisible by 4}}{\underbrace{4q·5}}+\underset{\text{divisible by 4}}{\underbrace{5-1}}\end{array}$
Therefore P_n TRUE for n = 1, 2, 3,...

---

MATH 122
MATHEMATICAL INDUCTION PROBLEMS

Use induction to prove that each of the following formulas is true for each positive integer n.

1.   $1^3+2^3+3^3+\cdots +n^3=\frac{n^2{\left(n+1\right)}^2}{4}$
2.   $1\cdot 2+3\cdot 4+5\cdot 6+\cdots +\left(2n-1\right)\left(2n\right)=\frac{n\left(n+1\right)\left(4n-1\right)}{3}$
3.   $\frac{1}{2}+\frac{2}{2}+\frac{3}{2}+\cdots +\frac{n}{2}=\frac{n\left(n+1\right)}{4}$
4.   $2+6+10+\cdots \left(4n-2\right)=2n^2$
5.   $2^1+2^2+2^3+\cdots +2^n=2^{n+1}-2$
6.   $1\cdot 2+2\cdot 3+3\cdot 4+\cdots +n\left(n+1\right)=\frac{n\left(n+1\right)\left(n+2\right)}{3}$
7.   $1\cdot 2^2+2\cdot 3^2+3\cdot 4^2+\cdots +n{\left(n+1\right)}^2=\frac{1}{12}n\left(n+1\right)\left(n+2\right)\left(3n+5\right)$

By induction show that:

8.   3ⁿ − 1 is divisible by 2.
9.   5ⁿ − 1 is divisible by 4.
10.   7ⁿ − 1 is divisible by 6.
11.   8²ⁿ − 1 is divisible by 63.
12.   6²ⁿ − 1 is divisible by 35.
13.   9²ⁿ − 1 is divisible by 80.
14.   n² − 3n + 4 is even.
15.   2n³ − 3n² + n is divisible by 6.
16.  
    1.  Show: If 2 + 4 + 6 + ... + 2n = n(n + 1) + 2 is true for n = j, then it is true for n = j + 1.
    2.   Is the formula true for all n?