The principle of induction says that if you have some $\mathbb N$ indexed family of propositions $P(n)$, that you can prove the theorem $\forall n \in \mathbb N, P(n)$ just by proving:
- $P(1)$
- $\forall n \in \mathbb N. P(n) \Rightarrow P(n+1)$
Intuitively this is quite simple, for any given number say 3051 the statement P(3051) must be true, since P(0) is true, P(1) is true, P(2) is true ... all the way up to P(3051). Mathematically this is just reflecting the nature of $\mathbb N$ so it's a tautology.
It is probably not clear what a proposition is though, because nobody ever talks about them. Well if you are familiar with functions, like $f(x) = x^2-1$, given any number say 3 you find that f(3) is a number too: 8. A proposition is like a function except that it computes a mathematical statement.
I could define the following proposition: $S(x) :\iff \exists n, n^2 = x$ and that would hold for all square numbers for example $S(9) \iff \exists n, n^2 = 9$ and so we can prove $S(9)$ by proving $\exists n, n^2 = 9$ by exhibiting the witness 3 then showing that $3^2 = 9$.
A much more interesting example might be the proposition $\text{Strong}_P(n)$ which is defined like so:
$\text{Strong}_P(1) :\iff P(1)$
$\text{Strong}_P(2) :\iff P(1) \text{ and } P(2)$
$\text{Strong}_P(3) :\iff P(1) \text{ and } P(2) \text{ and } P(3)$
...
$\text{Strong}_P(n+1) :\iff \text{Strong}_P(n+1) \text{ and } P(n+1)$
It is relatively easy to verify that $\text{Strong}_P(n) \iff (\forall k \leq n, P(k))$ so this really is the principle of "strong" induction. Furthermore you can prove the definition holds for all $n$ using normal induction.
A very beautiful theorem is that the sum of cubes is the square of the sum, e.g.
$$1^3 + 2^3 + 3^3 + 4^3 + 5^3 = (1 + 2 + 3 + 4 + 5)^2$$
So let $P(n)$ be the statement "sum of cubes up to n = square of sum up to n". Obviously it holds for P(1) since 1 = 1, now we would like to prove $\forall n \in \mathbb N. P(n) \Rightarrow P(n+1)$:
for all n, given that the sum of cubes up to n equals the square of the sum of to n, then "the same statement for n+1".
So we have the assumption $1^3 + 2^3 + \cdots + n^3 = (1 + 2 + \cdots + n)^2$ and need to prove $1^3 + 2^3 + \cdots + n^3 + (n+1)^3 = (1 + 2 + \cdots + n + n+1)^2$.
Now we use algebra, the right hand side is $(1 + 2 + \cdots + n)^2 + 2(n+1)(1 + 2 + \cdots + n) + (n+1)^2$. So all we have to show now is that $(n+1)^3 = 2(n+1)(1 + 2 + \cdots + n) + (n+1)^2$.
Multiplying out some things $n^3 + 3 n^2 + 3 n + 1 = 2(n+1)(1 + 2 + \cdots + n) + n^2 + 2 n + 1$ cancelling some things gives: $n (n + 1)^2 = 2(n+1)(1 + 2 + \cdots + n)$ and we quickly notice it being equivalent to the formula $(1 + 2 + \cdots + n) = n (n + 1)/2$.
Shall we try to prove this by induction also! Let $T(n)$ be the statement that $(1 + 2 + \cdots + n) = n (n + 1)/2$. Clearly T(1) holds, since 1 = 1. Now we should like to prove that for any given $n$ the hypothesis $T(n)$, that is $(1 + 2 + \cdots + n) = n (n + 1)/2$ implies that $(1 + 2 + \cdots + n + n+1) = (n + 1) (n + 2)/2$. Algebraically we can just substitute the hypothesis in to get $n (n + 1)/2 + n+1 = (n + 1) (n + 2)/2$ doubling this $n (n + 1) + 2 n + 2 = (n + 1) (n + 2)$ and this is obviously true by multiplying out both sides.
(this was a stupid example though beacuse you can just check the first 4 cases and not do any induction).