# Strong induction confusion

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

• There is a difference between induction and strong induction. Often times people are introduced to induction where they prove a base case, assume that the statement is true for all values up to k, and then show that k+1 is true. Strong induction proves a base, and then acknowledges k items, decreases down to k-1, applies the induction hypothesis to k-1, and then work back up to k, without breaking the property induced by the hypothesis. Normal induction doesn't specify that the k+1 object is achievable in some settings. Graph Theory is a good field for this. – Steve Schroeder Nov 21 '18 at 18:30
• I spent ll my time thinking that for normal induction we just assume it to be true for some k value not k and all below – hitherematey Nov 21 '18 at 18:32

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$$.

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.

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)$$...