# 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 '20 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. – Arthur Jan 27 '20 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? – super.t Jan 27 '20 at 14:25

## 1 Answer

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.