Question

Can someone explain proof by mathematical induction to me?

I can get down to the part where you have to prove the statement for `n=k+1`, and then I get confused and everything goes horribly wrong.

Answer 1

Here's the basis...

Explanation:

The 19th century Italian mathematician Giuseppe Peano presented what are known as the Peano postulates, describing a formal basis for arithmetic of Natural numbers.

In a modern formulation, here are Peano's axioms, describing the basic properties of the Natural numbers:

• `0` is a Natural number.

• If `n` is a Natural number then `sigma(n)` (the successor of `n`) is a Natural number.

• If `m` and `n` are Natural numbers then `m = n` if and only if `sigma(m) = sigma(n)`.

• For any Natural number `n`, `sigma(n) != 0`.

• If `P(n)` is a property such that `P(0)` and for any Natural number `n`, `P(n) => P(sigma(n))` then `P(n)` for all Natural numbers.

The last of these axioms is the axiom of induction and the basis of proof by induction.

Given Peano's axioms, we can define addition of Natural numbers as follows:

• `n + 0 = 0 + n = n` for any Natural number `n`.

• `m + sigma(n) = sigma(m) + n = sigma(m + n)` for any Natural numbers `m, n`.

If we define `1 = sigma(0)`, then we can rewrite the axiom of induction as:

• If `P(n)` is a property such that `P(0)` and for any Natural number `n`, `P(n) => P(n+1)` then `P(n)` for all Natural numbers.

So to prove that a proposition `P(n)` holds for an natural numbers `n` it is sufficient to prove `P(0)` and that if `P(n)` then `P(n+1)`.