proof by induction

Induction let’s us define objects and prove statements.

If we want to prove that a predicate $P$ is true for all natural numbers $n$, i.e. $\forall n\in \mathbb{N}:P(n)$, we can do the following:

1. Check $P(0)$ (the statement is true for $0$)
2. Check $\forall n:P(n)⟹P(n+1)$ (if the statement is true for $n+1$, it is also true for $n+1$; implication)

It may be, that something holds only for a subset of $\mathbb{N}$.
For example if something only holds only if $n$ is bigger than some $n_0\in \mathbb{N}$, i.e. $(\forall n\in \mathbb{N}:n\ge n_0):P(n)$, we just:

1. Check $P(n_0)$
2. Check $\forall n\ge n_0:P(n)⟹P(n+1)$

Statement: ${\sum }_{k=1}^{n}k=\frac{n(n+1)}{2}$

Induction basis: ${\sum }_{k=1}^1=\frac{1\cdot (1+1)}{2}=1$ $✓$
Hypothesis: Suppose basis is true: $\forall n\ge 1:{\sum }_{k=1}^{n}k=\frac{n(n+1)}{2}$
We need to show that $\forall n\ge 1:{\sum }_{k=1}^{n+1}k=\frac{(n+1)(n+2)}{2}$

$$\begin{array}{rl}\sum _{k=1}^{n+1}k& =\sum _{k=1}^{n}k+(n+1)\\ & =\frac{n(n+1)}{2}+(n+1)\text{ inserting hypothesis}\\ & =\frac{n(n+1)+2(n+1)}{2}\\ & =\frac{(n+1)(n+2)}{2}\text{ which was to be shown}\end{array}$$

Statement: ${\sum }_{k=1}^n(2k-1)=n^2$

Summing the first $n$ odd numbers $=n^2$ …
Induction basis: ${\sum }_{k=1}^{1}2-1=1^2$ $✓$
Hypothesis: Suppose basis is true: $\forall n\ge 1:{\sum }_{k=1}^n(2k-1)=n^2$
We need to show that: $\forall n\ge 1:{\sum }_{k=1}^{n+1}(2k-1)=(n+1{)}^2$

$$\begin{array}{rl}\sum _{k=1}^{n+1}(2k-1)& =\sum _{k=1}^n(2k-1)+(2(n+1)-1)\\ & =n^2+2n+1\text{ inserting hypothesis}\\ & =(n+1{)}^2\text{q.e.d}\end{array}$$

Statement: $P(n)=2^n>n+2$

$$\begin{array}{rl}P(0)& =2^0>0+2=1>2\text{false}\\ P(1)& =2^1>1+2=2>3\text{false}\\ P(2)& =2^2>2+2=4>4\text{false}\\ P(3)& =2^3>3+2=8>5\text{true}\end{array}$$

We suppose: $\forall n\ge 3:2^n>n+2$.
We need to show that $\forall n\ge 3:2^n+2⟹2^{n_{2+1}}>n+3$
Note: showing $P(3)$ holds is also called the “Induktions-Anfang”, the supposing was the “Induktionsvorraussetzung” and the step after that “Induktionsbehauptung”.
It would also be correct to prove by writing down the claim, and then rearranging to arrive at an obviously true statement - but it is not as clean, i.e. doesn’t show that we don’t conclude from the claim, but from the precondition.
$\text{Let}n\in \mathbb{N},2^n>n+2$

$$\begin{array}{r}((2^{n+1}=2\cdot 2^n)>(2n+4))=((n+3+\underset{>0}{\underbrace{n+1}})>(n+3))\end{array}$$

Transclude of strong-induction

proof by induction

$$\frac{K\cdots ⊢F\left[m/n\right]K\dots ,\bar{n}\in {\mathbb{N}}_{\ge m},F[\bar{n}/n]⊢F[(\bar{n}+1)/n]}{K\cdots ⊢\forall n\in {\mathbb{N}}_{\ge m}:F}$$

In words: To prove a property $F$ holds for all natural numbers $n\ge m$:
$K\cdots ⊢F\left[m/n\right]$ : Prove the base case, that $F$ holds for the smallest $n=m$.
$K\dots ,\bar{n}\in {\mathbb{N}}_{\ge m},F[\bar{n}/n]⊢F[(\bar{n}+1)/n]$ : Prove the inductive step, that for any arbitrary $\bar{n}\ge m$, if $F$ holds for $\bar{n}$, then it also holds for $\bar{n}+1$.
Then you can conclude $F$ holds for all $n\ge m$.

Link to original

Transclude of predicate-logic#^8c3317

Induktion in der Form funktioniert nur auf den natürlichen Zahlen or at least nicht in $\mathbb{R}$

Allgemeinerer Ramen:

Transclude of transfinite-induction

References

See TU Wien Mathematisches Arbeiten für mehr übungsbeispie.

http://mathfoundations.lti.cs.cmu.edu/class2/induction.html

Defining addition, subtraction, etc. via induction: See number theory, arithmetic, algebra.