Mathematical induction

One way of proving a mathematical theorem is called proof by induction. This is usually used to prove a theorem that is true for all numbers, especially natural numbers and integers. There are 4 steps in a proof by induction. It uses a domino effect, by proving the statement is true for one value, and then proving that it is true for the each successive case.

1. State that the proof will be by induction, and state which variable will be used in the induction step.

2. Show that the statement is true for some beginning case, usually the number 1.

3. Assume that for some value n, the statement is true. This is called the induction step.

4. Show that the statement is true for the next value, n+1.

Once that is shown, then it means that for any value of n that is true, the next one is true. Since it's true for some beginning case (usually n=1), then it's true for the next one (n=2). And since it's true for 2, it must be true for 3. And since it's true for 3, it must be true for 4, etc. Induction shows that it is always true, precisely because it's true for whatever comes after any given number.

An example of proof by induction:

Prove that for all natural numbers n:

[math]1+2+3+....+(n-1)+n=\tfrac12 n(n+1)[/math]

Proof:

First, the statement can be written: for all natural numbers n

[math]2\sum_{k=1}^n k=n(n+1)[/math]

By induction on n,

First, for n=1:

[math]2\sum_{k=1}^1 k=2(1)=1(1+1)[/math],

so this is true.

Next, assume that for some n=n₀ the statement is true. That is,:

[math]2\sum_{k=1}^{n_0} k = n_0(n_0+1)[/math]

Then for n=n₀+1:

[math]2\sum_{k=1}^{{n_0}+1} k[/math]

can be rewritten

[math]2\left( \sum_{k=1}^{n_0} k+(n_0+1) \right) [/math]

Since [math]2\sum_{k=1}^{n_0} k = n_0(n_0+1),[/math]

[math]2\sum_{k=1}^{n_0+1} k = n_0(n_0+1)+2(n_0+1) =(n_0+1)(n_0+2)[/math]

Hence the proof is correct.