Why proof by induction is working.

Question

I know how to make proofs by induction, but I don't understand why it prove that the propriety is true. It's in fact logical, but how to prove that proof by induction really prove the assertion.

Answer 1

I'm not sure what you are asking. There are two things involved:

1. Intuition. You prove that your statement is true for $n=1$, and then from this you show it's true for $n=2$, from that for $n=3$ etc., just you do all these steps in one step.

2. Axiom of induction. One of its versions is $$ \forall P \Bigl( \Bigl( \forall n \bigl( \forall m (m<n \implies P(m)) \implies P(n) \bigr) \Bigr) \implies \Bigl( \forall n (P(n)) \Bigr) \Bigr), $$ where $P$ is a formula with one variable, and $n$, $m$ are natural numbers. This is a simpler version of the one mentioned in wikipedia, because the first step -- proving that $P(0)$ is true, is an integral part of the statement.

Answer 2

Let prove the following theorem:

1) $A(0)$ true,

2) For all $n$ we have that $A(n)$ true $\implies A(n+1)$ true.

Then $A(n)$ is true for all $n$.

Let denote $$\mathcal W=\{n\mid A(n)\ \text{ is false}\}.$$ Suppose by contradiction that $A$ is not true, i.e. that $|\mathcal W|\neq\emptyset$. Since $\mathcal W\subset \mathbb N$ and that $\mathbb N$ is well ordered, there is an $\alpha\in \mathcal W$ which is minimal. By 1) we have that $\alpha\neq 0$. Therefore, by minimality of $\alpha$, we have that $A(\alpha-1)$ is true, which is a contradiction with 2). Therefore $A(n)$ is true for all $n$.

Answer 3

$\bf Definition:$ Inductive set.

An inductive set is a set S that satisfies:

1. $1\in S$.

2. $k\in S\implies k+1\in S$.

$\bf Definition: \Bbb N$

$\Bbb N$ is the set that satisfies:

1. $\Bbb N$ is inductive.

2. If $H$ is inductive, then $\Bbb N \subseteq H$.

Consider now, some proposition $P(n)$. Let $T=\{n\in \Bbb N: P(n)\}$ be the set of $n\in \Bbb N$ that make the proposition true..

Now, if we prove that $T$ is inductive, we will have proved that $T=\Bbb N$ (as we have from it's definition that $T\subseteq\Bbb N$): the proposition is true for all natural $n$.

Answer 4

A proposition is true when $n=1$.

If it is true when $n=1$, then it is true when $n=2$.

If it is true when $n=2$, then it is true when $n=3$.

If it is true when $n=3$, then it is true when $n=4$.

If it is true when $n=4$, then it is true when $n=5$.

If it is true when $n=5$, then it is true when $n=6$.

and so on${}\,\ldots$

If this sequence can be shown to keep going, then it is true when $n$ is equal to any of $1,2,3,4,\ldots\,{}$. That is induction.