0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Steve Schroeder Nov 21 '18 at 18:30
  • $\begingroup$ 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 $\endgroup$ – hitherematey Nov 21 '18 at 18:32
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.