# 9231. FP1. Induction

As you get closer towards university level maths, proof becomes very important.

Inductive proof can be used if we suspect something to be true. Metaphorically it is like proving an infinite ladder exists by first showing that the bottom rung of the ladder exists (the initial step) and then showing that if any rung of the ladder exists then the rung above it must necessarily also exist (the inductive step). If we have shown these two steps to be true, then we have proved that the ladder exists.

This process is easiest seen by way of some examples

Worked Examples – Sum of Series

• Prove, by mathematical induction, that
• $\sum_{r=1}^{n}r = \frac{1}{2}n(n+1)$
• $\sum_{r=1}^{n}(r^2-r) = \frac{n(n^2-1)}{3}$ for all n≥1

This method of proof can be used in many different areas of mathematics, and not just summation of series.

Worked Examples – Differentiation

• Prove, by mathematical induction, that
• If y = e2x, then $\frac{d^ny}{dx^n} = 2^ne^{2x}$
• The 2nth derivative of y = cos(1-2x) is $\frac{d^{2n}y}{dx^{2n}} = (-1)^n2^{2n}cos(1-2x)$

Worked Examples – Recurrence Relations

• Prove the following two problems using mathematical induction:
• If $u_{n+1} = \frac{5u_n-2}{u_n+2}$, where u1 = 5, show that un>2 for all n≥1
• If $u_{n+1} = 3u_n+2$, where u1 = 1, show that un = 2 x 3n-1 -1 for all n ≥ 1

Worked Example – Matrices

Prove by induction that $\begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}^n = \begin{pmatrix} 2^n & 2^n-1 \\ 0 & 1 \end{pmatrix}$

Exercise

Proof of divisibility

Consider proving that f(n) = 22n+2+5 is divisible by 3 for all n≥0. For our inductive step we consider f(k+1) – f(k)

• f(k+1) – f(k) = 22(k+1)+2+5 – 22k+2+5 = 22k+4 – 22k+2
• This equal 22k(24-22) = 12 x 22k, which is clearly divisible by 3.

So as f(k+1) – f(k) is divisible by 3, if we assume f(k) is divisible by 3, it follows that f(k+1) is also divisible by 3. So we can complete a full inductive proof.

Worked Example

A function is defined as f(n) = 3n+2 + 5. Using mathematical induction, prove that 3n+2+5 is always divisible by 2 for n≥0.

The exact same method can be used with polynomials

Worked Example

A function is given as f(n) = (n+2)3 + (2n+1)3. Prove by induction that f(n) is divisible by 3 for all values n ≥ 0.

Exercise & General Exercises