Proof by Mathematical Induction

Proof by mathematical induction

Mathematical induction is the process of verifying or proving a mathematical statement is true for all values of $n$ within given parameters. For example:

$\text{Prove that }f(n)=5^n+8n+3\text{ is divisible by }4,\text{ for }n\in {\mathbb{Z}}^{+}$

We are asked to prove that $f(n)$ is divisible by 4. We can test if it's true by giving $n$ values.

$n$	$f(n)$	$\text{Divisible by }4$
$1$	$16$	$4\cdot 4$
$2$	$44$	$4\cdot 11$
$3$	$152$	$4\cdot 38$
$4$	$660$	$4\cdot 165$
$5$	$3168$	$4\cdot 792$

So, the first 5 values of n are divisible by 4, but what about all cases? That's where mathematical induction comes in.

Mathematical induction is a rigorous process, as such all proofs must have the same general format:

1. Proposition – What are you trying to prove?
2. Base case – Is it true for the first case? This means is it true for the first possible value of $n$.
3. Assumption – We assume what we are trying to prove is true for a general number. such as $k$, also known as the induction hypothesis.
4. Induction – Show that if our assumption is true for the ($k^{th})$ term, then it must also be true for the ($k+1^{th})$ term.
5. Conclusion – Formalise your proof.

There will be four types of mathematical induction that you will come across in FP1:

1. Summation of series;
2. Divisibility;
3. Recurrence relations;
4. Matrices.

Example of a proof by summation of series

(Empty)

Example of a proof by divisibility

Proposition: $\text{Prove that }4|f(n)=5^n+8n+3,\text{ for }n\in {\mathbb{N}}^{+}$

Notice our parameter, $\text{for }n\in {\mathbb{N}}^{+}$ . This means that what we want to prove must be true for all values of $n$ which belong to the set (denoted by $\in$) of positive integers (${\mathbb{N}}^{+}$).

Base case:

$\begin{array}{cc}& \text{Let }n=1\\ & f(1)=5^1+8(1)+3⟹f(1)=16\\ & \therefore 4|f(1)\end{array}$

Assumption (Induction Hypothesis): Now we let $n=k$ where $k$ is a general positive integer, and we assume that $4|f(k)$.

Remember that $f(k)=5^k+8k+3$.

Induction: Now we want to prove that the $k+1^{th}$ term is also divisible by 4

Hence:$\text{let }n=k+1⟹f(k+1)=5^{k+1}+8(k+1)+3$

This is where our assumption comes in, if $4|f(k)$ then 4 must also divide $f(k+1)-f(k)$.

So: $f(k+1)-f(k)=5^{k+1}+8(k+1)+3-(5^k+8k+3)$

$\begin{array}{cc}& f(k+1)-f(k)=5(5^k)-5^k+8\\ & f(k+1)-f(k)=4(5^k)+8\\ & \therefore f(k+1)-f(k)=4(5^k+2)\end{array}$

Now we've shown $4|(f(k+1)-f(k))$ and thus $4|f(k+1)$. This implies that $4|f(n)$ because you have successfully shown that 4 divides $f(n)$, where $n$ is a general, positive integer ($k$) and also the consecutive term after the general term ($k+1$)

Conclusion:

$\begin{array}{cc}& 4|f(k)⟹4|f(k+1)\\ & \therefore 4|f(n),\mathrm{\forall }n\in {\mathbb{Z}}^{+}\end{array}$

$\begin{array}{cc}& \text{If }4\text{ divides }f(k)\text{ (as we assumed) then it implies that }4\text{ also divides }f(k+1)\\ & \text{therefore }4\text{ divides }f(n),\text{ for all values of }n\text{ that belong to the set of positive integers.}\end{array}$

Example of a proof by recurrence relations

(Empty)

Example of a proof by matrices

(Empty)