Intro to Proof by Induction (Edexcel A-Level Further Mathematics): Revision Notes

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

Step 1: Prove for the base case

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$):

Assuming $2^k > 1 + k$ :

Make the RHS of our target appear here:

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

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$ .

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

Step 1: Base case

Step 2: Assumption

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

Step 3: Inductive Step

Assuming $2^k > 2k$:

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$.

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

Step 1: Base case

Step 2: Assumption

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

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

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

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

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$.