6.3 Proof by induction
Definition 6.3.1
The principle of mathematical induction states that if we have a statement which depends on a natural number $n$ and

•
if the statement is true for $n=s$ ($s$ is some natural number, usually $0$ or $1$)

•
and for every natural number $k\geqq s$ if the statement is true for $n=k$, then the statement must also be true for $n=k+1$
then the statement is true for every $n\geqq s$.
One way of thinking about induction is by considering an analogy to dominoes. If we have a row of dominoes, and we knock one domino over, and knocking any given domino over means that the next one over, then all the dominoes will fall over.
A general formula for solving any induction problem involving property $P(n)$ reads something like:

•
The basis step  show that $P(a)$ is true.

•
The inductive step  show that if $P(k)$ is true, then this implies that $P(k+1)$ is also true.

•
The completion step  write some words stating that as $P(a)$ is true and $P(k)$ being true implies $P(k+1)$ is true, $P(n)$ must be true for all integer $n$ with $n\geqq a$.
It probably helps to include some examples (see the next sections).
6.3.1 Divisibility
Example 6.3.1
Let the function $f(x)$ be defined by
Show that for all $n\in\mathbb{N_{0}}$, $f(n)$ is divisible by 7.
The first step is the basis case. By calculation $f(1)=2^{2}+5\cdot 9=49$ (which is divisible by $7$, as $7\cdot 7=49$).
The next step is the inductive step. Here we assume that $f(k)$ is divisible by $7$, and then consider $P(k+1)$.
The key thing here is to apply the inductive hypothesis (aka the fact that we have assumed that $f(k)$ is divisible by $7$). This is pretty much always the first thing to do!
We know that $f(k)=2^{k+1}+5\cdot 9^{k}$. Currently, this doesn’t help very much as we have no way to apply it to the equation above. What we can do, however, is rearrange it to express either $2^{k+1}$ or $5\cdot 9^{k}$ in terms of $P(k)$ and the other term. In this case, we’ll choose to eliminate $2^{k+1}$, but we could do it the other way, and it would be fine.
$\displaystyle P(k)=2^{k+1}+5\cdot 9^{k}$  (6.5)  
$\displaystyle 2^{k+1}=P(k)5\cdot 9^{k}$  (6.6) 
We can now apply this to $P(k+1)$, by taking out a factor of $2$ from $2^{k+1+1}$ and then substituting.
$\displaystyle P(k+1)$  $\displaystyle=2^{k+1+1}+5\cdot 9^{k+1}$  (6.7)  
$\displaystyle=2\cdot 2^{k+1}+5\cdot 9^{k+1}$  (6.8)  
$\displaystyle=2\left(P(k)5\cdot 9^{k}\right)+5\cdot 9^{k+1}$  (6.9) 
Now we can factorise the expression, and hopefully find a factor of $7$ lurking somewhere!
$\displaystyle P(k+1)$  $\displaystyle=2\left(P(k)5\cdot 9^{k}\right)+5\cdot 9^{k+1}$  (6.10)  
$\displaystyle=2P(k)10\cdot 9^{k}+5\cdot 9^{k+1}$  (6.11)  
$\displaystyle=2P(k)10\cdot 9^{k}+5\cdot 9\cdot 9^{k}$  (6.12)  
$\displaystyle=2P(k)+35\cdot 9^{k}$  (6.13) 
This means that $P(k)$ being divisible by $7$ implies that $P(k+1)$ is also divisible by $7$.
Now onto the completion step! This is pretty much the same every time: \say Thus $P(n)$ implies $P(n+1)$ and as $P(1)$ is true, $P(n)$ holds for all $n\in\mathbb{N}$ where $n\geqq 1$.
6.3.2 From $k$ to $k+1$
Sometimes it can be more practical to work from the case $n=k$ and apply operations to that to form the case $n=k+1$, rather than trying to expose $n=k$ within $n=k+1$ (i.e. write the case $n=k+1$ in terms of $n=k$).
TODO: example