Strong induction confusion

Question

In strong induction i do not understand why lets say you proved the base case

n=1

Then you assumed that the statement is true for all n from 1 to k, where k is some number in N.

And in the induction step you need to use the truth of say k-2, so k-2 has to be in that range above which is true when k is 3 or greater, so you add two more base cases, n=2 and n=3.

What i do not understand is what if k=7 then we used the truth of the statment for n=5 which was not included in the base case?

So can someone explain to me what is going on in the base case and induction step of strong induction because i do not get it. THank you for your time

Answer 1

Assume you have a proof of

If $n\in\Bbb N$ and $n-2\in \Bbb N$ and $\Phi(n-2)$ is true, then $\Phi(n)$ is true.

Then $\Phi(7)$ follows from $\Phi(5)$. If you did not show $\Phi(5)$ as a base case, $\Phi(5)$ can alsoe be concluded from $\Phi(3)$. And if $\Phi(3)$ is still not among the base cases, you can conclude it anyway from $\Phi(1)$. But (hopefully), you already know that $\Phi(1)$ is true (base case).

Note that in this specific scenario, you need to show $\Phi(1)$ and $\Phi(2)$ "manually". Everything else follows by induction as just illustrated by the argument for $n=7$.

More formally, the set $$X:= \{\,n\in\Bbb N\mid\Phi(n)\text{ is false}\,\}$$ is a subset of $\Bbb N$. Assume $X\ne \emptyset$. Then $X$ has a minimal element $n_0$. Then $n_0$ cannot be $>2$ as we would arrive at a contradiction with the induction step statement. Hence either $n_0=2$ or $n_0=1$; but by direct proofs for $\Phi(1)$ and $\Phi(2)$, we know that $1,2\notin X$. from this contradiction, we infer that $X=\emptyset$.

Answer 2

In strong induction you assume the statement is true for all numbers up to $k$ and prove it for $k+1$. If you only need the truth of $k-2$ to prove it for $k$ you can use regular induction once you prove the base cases $1,2$ because all the odd numbers feed off $1$ and all the even numbers feed off $2$.

One example is the fundamental theorem of arithmetic, that every number can be written as a product of primes. $1$ is the empty product, $2$ and $3$ are primes, $4=2\cdot 2$ and so on. Assume it is true for all the numbers up to $k$. Then $k+1$ is either prime and we can write it as $k+1$ or we can write $k+1=pq$ for numbers $p,q$ that are both greater than $1$ and less than $k+1$. They can therefore be decomposed into primes-this is where we use the fact that all numbers less than or equal to $k$ can be decomposed.

Answer 3

Inductive step

We must show $\forall n\in \mathbb{N},\quad \big[\forall i\in [\![0,n]\!],\;P(i)\big]\implies P(n+1)$

When it is done that is equivalent to

\begin{array}{rl}P(0)&\implies P(1) \\P(0) \;\text{and}\; P(1)&\implies P(2)\\P(0) \;\text{and}\; P(1)\;\text{and}\;P(2)&\implies P(3)\\\\\vdots\\P(1)\;\text{and}\;P(2)\;\text{and}\cdots\;P(n)&\implies P(n+1)\\\\ \vdots\end{array}

Base case

At the moment we know nothing about any $P(i)$ so we have to test if $P(0)$ is right. If it is, from it you deduce $P(1)$ then from $P(0)$ and $P(1)$ (we know they are both right) you deduce $P(2)$...