9.1.1 Intro to Proof by Induction

What is Proof by Induction?

Mathematical induction is a method used to prove statements or formulas that depend on a positive integer $n$ .

It involves verifying that a statement is true for $n = 1$ and then proving that if it is true for $n = k$ , it must also be true for $n = k+1$ .

Base Case: Verify that the statement is true for $n = 1$ (or the smallest integer specified in the problem).
Inductive Hypothesis: Assume the statement is true for $n = k$ . This is called the inductive assumption.
Inductive Step: Using the inductive hypothesis, prove the statement is true for $n = k+1$
Conclusion: Conclude that the statement is true for all integers $n \geq 1$ (or the specified starting value).

lightbulbExample

Example Prove $2^n > 1 + n$ for all $n \geq 2 , n \in \mathbb{N}$ .

Step 1: Prove for the base case

\text{Let } n = 2 \quad \Rightarrow \quad \text{LHS} = 2^2 = 4

\text{RHS} = 1 + 2 = 3

\text{LHS} > \text{RHS} \quad \text{true for } n = 2

Step 2: Assume true for $n = k$

Let $n = k$ and assume true, i.e. $2^k > 1 + k$ .

Step 3: Let $n = k + 1$ and prove true using assumption

At this point, look at what we need to do to the LHS of our assumption to get the LHS of our target:

Target (Inequality with $n = k + 1$ ):

2^{k + 1} > k + 2

Assuming $2^k > 1 + k$ :

\Rightarrow 2(2^k) > 2(1 + k)

\Rightarrow 2^{k+1} > 2 + 2k

Make the RHS of our target appear here:

2^{k+1} > (k + 2) + k \gt k + 2

Since $k \gt 0$ for $k \geq1$ (always state range of values for which true)

\therefore 2^{k + 1} > k + 2

Multiplying both sides of our assumption by 2 gives another statement we can assume true.

Step 4: Conclude

If true for $n = k$ , then true for $n = k + 1$ .

Since true for $n = 2$ , then true for all integers $n \geq 2$ .

lightbulbExample

Example Prove $2^n > 2n$ for $n \geq 3$ , $n \in \mathbb{N}$

Step 1: Base case

\text{Let } n = 3 \quad \Rightarrow \quad \text{LHS} = 2^3 = 8, \quad \text{RHS} = 2(3) = 6

\text{LHS} > \text{RHS} \quad \therefore \text{true for } n = 3

Step 2: Assumption

Let $n = k$ and assume true, i.e. $2^k > 2k$ .

Step 3: Inductive Step

Assuming $2^k > 2k$ :

2(2^k) > 2(2k)\\ \text {Multiply the LHS of our assumption by 2 to get the LHS of our target}

\Rightarrow 2^{k+1} > 4k

\Rightarrow 2^{k+1} \gt (2k + 2) + (2k - 2)\gt 2k + 2 \\ \quad \text{Must be equal to the above line to be true}

\text{since } 2k - 2 > 0 \text{ for } k \geq 2

\Rightarrow 2^{k+1} > 2k + 2

Step 4: Conclusion If true for $n = k$ , then true for $n = k + 1$ . Since true for $n = 3$ , then true for all integers $n \geq 3$ .

lightbulbExample

Example Prove that $n! > 2^n$ for all $n \geq 4$ , $n \in \mathbb{N}$

Step 1: Base case

\text{Let } n = 4 \quad \Rightarrow \quad \text{LHS} = 4! = 24, \quad \text{RHS} = 2^4 = 16

\text{LHS} > \text{RHS} \quad \therefore \text{true for } n = 4

Step 2: Assumption

Let $n = k$ and assume true, i.e. $k! > 2^k$ .

Step 3: Inductive step Assuming $k! > 2^k$ :

\text{TARGET: } (k+1)! > 2^{k+1}

(k+1)k! > (k+1)2^k\\

Multiply both sides by $k+1$ to get LHS of the target.

\Rightarrow (k+1)! > 2 \times 2^k

We have made RHS smaller, so " $\gt$ "still holds.

\text{Since } k+1 \geq 2 \text{ when } k \geq 2

\Rightarrow (k+1)! > 2^{k+1}

Conclusion If true for $n = k$ , then true for $n = k+1$ . Since true for $n = 4$ , then true for all integers $n \geq 4$ .