1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Dirk Jan 27 '20 at 11:40
  • 1
    $\begingroup$ @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. $\endgroup$ – Arthur Jan 27 '20 at 11:45
  • $\begingroup$ @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? $\endgroup$ – super.t Jan 27 '20 at 14:25
1
$\begingroup$

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.

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