# How is the inductive hypothesis in strong mathematical induction different from that in ordinary induction?

I don't understand how supposing that $$P(k), k\geq 1$$ for ordinary induction is different from $$P(i), 1 \leq i \leq k, k\geq1$$ for strong induction. Example from quora:

Letβs say you wanted to prove that every positive integer has a prime factorization $$π_1π_2π_3...π_π$$.

Let π(π) be the statement that an integer π has a prime factorization. Weβll proceed by strong induction. The basis is pretty clear, so Iβll leave it out.

Next weβll assume that π(1),π(2),π(3),...,π(π) are true. π+1 can either be prime or composite, and if itβs prime weβre done, so weβll assume itβs composite. That means π+1 can be written as a product of two positive integers, i.e. π+1=ππ, with $$π,πββ€^+$$. We can write 1<π<π+1, and 1<π<π+1, which implies that 2β€πβ€π and 2β€πβ€π.

Here is why we need strong induction: if we had simply supposed π(π) was true for arbitrary π, we would be stuck. However, we supposed that π(π) was true for every positive integer up to π=π, so we have much more information to work with. Because we supposed this, we know that π(π) and π(π) are true, i.e. that π and π can be represented as a product of primes. We were able to reduce the problem down to a point where π and π were in a range, and since our inductive hypothesis in strong induction supposes that π(π) is true for a range of values (rather than just one arbitrary π), we can now use it to prove the truth of π(π+1).

Using ordinary induction, I'd say that $$P(p)$$ and $$P(q)$$ are true because $$2β€πβ€π$$ and $$2β€πβ€π$$ and $$P(k), k\geq 1$$. Why can I not use ordinary induction here?

Another example is the proof that McCarthy 91 function equals 91 for all positive integers less than or equal to 101. The property is $$P(n)=M(101-n), n \geq 0$$ and $$M(n)$$ is the McCarthy function. The author of the proof calculates the base case for $$P(0)$$, then does a supposition that $$P(i), 0 \leq i \leq k, k \geq 0$$. The use of strong induction is justified by the fact that we need the inductive hypothesis to hold for $$k-10$$, but I don't see why $$P(n), n\geq0$$ wouldn't hold for $$n=k-10, k\geq11$$, that is $$n$$ is at least 1, if ordinary induction was used.

• For ordinary induction, you wouldn't assume $P(p)$ and $P(q)$. When proving the theorem for $k+1$, you would assume $P(k)$, and only $P(k)$ (otherwise you are doing strong induction again). And that doesn't help you at all for the prime numbers.
– Dirk
Jan 27, 2020 at 11:40
• @Dirk Technically, you can do it with weak induction. Weak and strong are probably equivalent. However, in this case, using weak looks like a complete mess. Jan 27, 2020 at 11:45
• @Dirk right, in weak induction I make an assumption that the property holds only for the term immediately before (k+1) and prove that it holds for (k+1). p and q from the proof above do not necessary equal k, therefore I can't assume that P(q) and P(p) are true, and that's where strong induction helps with its "extended" assumption. Is it correct? Jan 27, 2020 at 14:25

Ordinary or weak induction proves $$Q(n)$$ for all $$n\ge1$$ with a base step $$n=1$$ and an inductive step from $$n=k$$ to $$n=k+1$$.
Complete or strong induction considers the special case where $$Q(n)$$ denotes "$$P(k)$$ for all $$k$$ from $$1$$ to $$n-1$$ inclusive". If we try to prove $$Q(n)$$ for all $$n\ge1$$ by weak induction, the base step is vacuously true, and the inductive step is showing that, if $$P(k)$$ for all $$k$$ from $$1$$ to $$n-1$$ inclusive, then $$P(n)$$. If we can prove this statement, the weak induction on $$Q$$ succeeds, and we have also proven $$P(n)$$ for all $$n\ge1$$.
In other words, strong induction states this: if "$$P(k)$$ for all $$k$$ from $$1$$ to $$n-1$$" implies $$P(n)$$, then $$P(n)$$ for all $$n\ge1$$. Usually, the $$n-1$$ is called $$n$$ instead, so we need to prove "$$P(k)$$ for all $$k$$ from $$1$$ to $$n$$" implies $$P(n+1)$$.
Unlike weak induction, strong induction does not in general need a base step. However, in some cases the argument proving its inductive step has to consider small values of $$n$$ as special cases.