Can someone explain proof by mathematical induction to me?

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$ $n=k+1$ , and then I get confused and everything goes horribly wrong.

1 Answer

Impact of this question

1374 views around the world

You can reuse this answer
Creative Commons License

Answer 1 · 2017-08-21T20:39:23

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$ $0$ is a Natural number.
If $n$ $n$ is a Natural number then $σ (n)$ $sigma(n)$ (the successor of $n$ $n$ ) is a Natural number.
If $m$ $m$ and $n$ $n$ are Natural numbers then $m = n$ $m = n$ if and only if $σ (m) = σ (n)$ $sigma(m) = sigma(n)$ .
For any Natural number $n$ $n$ , $σ (n) \neq 0$ $sigma(n) != 0$ .
If $P (n)$ $P(n)$ is a property such that $P (0)$ $P(0)$ and for any Natural number $n$ $n$ , $P (n) \Rightarrow P (σ (n))$ $P(n) => P(sigma(n))$ then $P (n)$ $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$ $n + 0 = 0 + n = n$ for any Natural number $n$ $n$ .
$m + σ (n) = σ (m) + n = σ (m + n)$ $m + sigma(n) = sigma(m) + n = sigma(m + n)$ for any Natural numbers $m, n$ $m, n$ .

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

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

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

Science

Math

Humanities

... and beyond

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$ $n=k+1$ , and then I get confused and everything goes horribly wrong.

1 Answer

Explanation:

Related questions

Impact of this question

Science

Math

Humanities

... and beyond

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+1n=k+1, and then I get confused and everything goes horribly wrong.

1 Answer

Explanation:

Related questions

Impact of this question

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