Proof by mathematical induction[1]

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

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

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

${\displaystyle n}$ ${\displaystyle f(n)}$ ${\displaystyle Divisible\ by\ 4}$
${\displaystyle 1}$ ${\displaystyle 16}$ ${\displaystyle 4*4}$
${\displaystyle 2}$ ${\displaystyle 44}$ ${\displaystyle 4*11}$
${\displaystyle 3}$ ${\displaystyle 152}$ ${\displaystyle 4*38}$
${\displaystyle 4}$ ${\displaystyle 660}$ ${\displaystyle 4*165}$
${\displaystyle 5}$ ${\displaystyle 3168}$ ${\displaystyle 4*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. basis 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 ${\displaystyle k}$
4. Induction - Show that if our assumption is true for the (${\displaystyle k^{th})}$ term, then it must be true for the term after (${\displaystyle k+1^{th})}$term.
5. Conclusion - Formalise your proof.

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

1. Summing series
2. Divisibility
3. Recurrence relations
4. Matrices

Example of proofs by Induction involving Summing series

Proposition: ${\displaystyle Prove\ by\ induction\ that,\displaystyle \sum _{r=1}^{n}r^{3}={\frac {1}{4}}n^{2}(n+1)^{2}}$${\displaystyle ,for\ n\in \mathbb {N^{+}} }$

Note our parameter, ${\displaystyle for\ n\in \mathbb {N^{+}} }$ This means it wants us to prove that it's true for all values of ${\displaystyle n}$ which belong to the set(${\displaystyle \in }$) of positive integers (${\displaystyle \mathbb {N^{+}} }$)

Basis case:

${\displaystyle Let\ n=1\ }$

${\displaystyle \displaystyle \sum _{r=1}^{1}r^{3}=1^{3}\ [LHS]}$
${\displaystyle {\frac {1}{4}}1^{2}(1+1)^{2}=1\ [RHS]}$

The Left hand side of our equation is equal to the right hand side of our equation, therefore our basis case holds true.

${\displaystyle LHS=RHS\longrightarrow \displaystyle \sum _{r=1}^{n}r^{3}={\frac {1}{4}}n^{2}(n+1)^{2},for\ n=1}$

${\displaystyle Now,\ let\ n=k\ and\ assume\ true\ \forall \ k\in \mathbb {Z^{+}} }$

This is what we are assuming to be true for all values of K which belong to the set of positive integers:

${\displaystyle \displaystyle \sum _{r=1}^{k}r^{3}={\frac {1}{4}}k^{2}(k+1)^{2}}$

Induction: For the induction we need to utilise the fact we are assuming ${\displaystyle n=k}$ to be true, as such we can just add on another term ${\displaystyle (k+1)}$ to the summation of the ${\displaystyle k^{th}}$ term in the series to give us the summation of the ${\displaystyle (k+1)^{th}}$ term of the series:

${\displaystyle Hence,\ let\ n=k+1:\displaystyle \sum _{r=1}^{k+1}r^{3}=\displaystyle \sum _{r=1}^{k}r^{3}+(k+1)^{3}}$

${\displaystyle \displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}k^{2}(k+1)^{2}+(k+1)^{3}}$

Factoring out ${\displaystyle {\frac {1}{4}}(k+1)^{2}}$ we get:

${\displaystyle \displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}(k+1)^{2}[k^{2}+4(k+1)]}$


This gives us: ${\displaystyle \displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}(k+1)^{2}(k+2)^{2}}$
Note we know that we're finished because, looking at what we were originally asked to prove, the ${\displaystyle n}$ values are replaced with ${\displaystyle k+1}$.

Summary:

${\displaystyle \therefore \ true\ for\ n=k+1\longrightarrow \ true\ \forall \ n\in \mathbb {Z^{+}} }$
Therefore, if our assumption is true for ${\displaystyle n=k}$ then ${\displaystyle n=k+1}$ is also true, which implies that ${\displaystyle n}$ is true for all values of ${\displaystyle n}$ that belong to the set of positive integers.

Example of a proof by induction involving Divisibility

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

Again, note our parameter, ${\displaystyle for\ n\in \mathbb {N^{+}} }$ This means it wants us to prove that it's true for all values of ${\displaystyle n}$ which belong to the set(${\displaystyle \in }$) of positive integers (${\displaystyle \mathbb {N^{+}} }$)

Basis case:

${\displaystyle Let\ n=1}$

${\displaystyle f(1)=5^{1}+8(1)+3\Rightarrow f(1)=16}$

${\displaystyle \therefore \ 4\ |\ f(1)}$

Assumption: Now we let ${\displaystyle n=k}$ where ${\displaystyle k}$ is a general positive integer and we assume that ${\displaystyle 4\ |\ f(k)}$

Remember ${\displaystyle f(k)=5^{k}+8k+3}$

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

Hence ${\displaystyle let\ n=k+1\rightarrow \ f(k+1)=5^{k+1}+8(k+1)+3}$

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

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

${\displaystyle f(k+1)-f(k)=5(5^{k})-5^{k}+8}$ ${\displaystyle f(k+1)-f(k)=4(5^{k})+8}$ ${\displaystyle \therefore f(k+1)-f(k)=4(5^{k}+2)}$

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

Conclusion:

If ${\displaystyle 4\ |\ f(k)\Rightarrow 4\ |\ f(k+1)}$
${\displaystyle \therefore \ 4\ |\ f(n),\forall \ n\in \mathbb {Z^{+}} }$

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