Mathematical Induction

 

Prove by mathematical induction \[ 9^{n} + 3 \] is divisible by 4 for all natural numbers \( n \gt 0 \).

Prove the statement is true for a particular n. Here n = 1 is a reasonable choice.

To show this is true for n=1, observe that the expression = 12. Now 12 is divisible by 4, so the statement is true for n = 1.

Assume the statement is true for n = k and show it is true for n = k + 1.

To show the statement is true for n = k+1, \[ \begin{align} 9^{(k+1)} + 3 &= 9 \times 9^k + 3 \\ \end{align} \ \]

Use the inductive hypothesis to simplify the right hand side.

By the inductive hypothesis, \[ \begin{align} 9 \times 9^{k} + 3 &= 9 \times (4m-3) + 3 \quad \text{for some integer m}\\ &= 9 \times 4 m - 27 + 3 \\ &= 4 \times 9m - 24 \\ &= 4 \times (9m - 6) \end{align} \ \] Which is divisible by 4. So the statement is true for n = k+1.

By the principle of mathematical induction,

The statement is true for \( n \gt 0 \).

You will gain most benefit if you work through each problem first and then come back and check your work against the solution.

 

y

Now You Try:

Prove by mathematical induction \[ 6^n + 4 \] is divisible by 10 for all natural numbers \( n \gt 0 \).