I am having trouble seeing the difference between weak and strong induction.
There are a few examples in which we can see the difference, such as reaching the $k^{th}$ rung of a ladder and proving every integer $>1$ can be written as a product of primes:
To show every $n\ge2$ can be written as a product of primes, first we note that $2$ is prime. Now we assume true for all integers $2 \le m<n$. If $n$ is prime, we're done. If $n$ is not prime, then it is composite and so $n=ab$, where $a$ and $b$ are less than $n$. Since $a$ and $b$ are less than $n$, $ab$ can be written as a product of primes and hence $n$ can be written as a product of primes. QED
However, it seems sort of like weak induction, only a bit dubious. In weak induction, we show a base case is true, then we assume true for all integers $k-1$, (or $k$), then we attempt to show it is true for $k$, (or $k+1$), which implies true $\forall n \in \mathbb N$.
When we assume true for all integers $k$, isn't that the same as a strong induction hypothesis? That is, we're assuming true for all integers up to some specific one.
As a simple demonstrative example, how would we show $1+2+\cdots+n= {n(n+1) \over 2}$ using strong induction?
(Learned from Discrete Mathematics by Kenneth Rosen)
Best Answer
Initial remarks: Good question. I think it deserves a full response (warning: this is going to be a long, but hopefully very clear, answer). First, most students do not really understand why mathematical induction is a valid proof technique. That's part of the problem. Second, weak induction and strong induction are actually logically equivalent; thus, differentiating between these forms of induction may seem a little bit difficult at first. The important thing to do is to understand how weak and strong induction are stated and to clearly understand the differences therein (I disagree with the previous answer that it is "just a matter of semantics"; it's not, and I will explain why). Much of what I will have to say is adapted from David Gunderson's wonderful book Handbook of Mathematical Induction, but I have expanded and tweaked a few things where I saw fit. That being said, hopefully you will find the rest of this answer to be informative.
Gunderson remark about strong induction: While attempting an inductive proof, in the inductive step one often needs only the truth of $S(n)$ to prove $S(n+1)$; sometimes a little more "power" is needed (such as in the proof that any positive integer $n\geq 2$ is a product of primes--we'll explore why more power is needed in a moment), and often this is made possible by strengthening the inductive hypothesis.
Kenneth Rosen remark in Discrete Mathematics and Its Applications Study Guide: Understanding and constructing proofs by mathematical induction are extremely difficult tasks for most students. Do not be discouraged, and do not give up, because, without doubt, this proof technique is the most important one there is in mathematics and computer science. Pay careful attention to the conventions to be observed in writing down a proof by induction. As with all proofs, remember that a proof by mathematical induction is like an essay--it must have a beginning, a middle, and an end; it must consist of complete sentences, logically and aesthetically arranged; and it must convince the reader. Be sure that your basis step (also called the "base case") is correct (that you have verified the proposition in question for the smallest value or values of $n$), and be sure that your inductive step is correct and complete (that you have derived the proposition for $k+1$, assuming the inductive hypothesis that proposition is true for $k$--or the slightly strong hypothesis that it is true for all values less than or equal to $k$, when using strong induction.
Statement of weak induction: Let $S(n)$ denote a statement regarding an integer $n$, and let $k\in\mathbb{Z}$ be fixed. If
then for every $n\geq k$, the statement $S(n)$ holds.
Statement of strong induction: Let $S(n)$ denote a statement regarding an integer $n$. If
then for every $n\geq k$, the statement $S(n)$ is true.
Proof of strong induction from weak: Assume that for some $k$, the statement $S(k)$ is true and for every $m\geq k, [S(k)\land S(k+1)\land\cdot\land S(m)]\to S(m+1)$. Let $B$ be the set of all $n>m$ for which $S(n)$ is false. If $B\neq\varnothing, B\subset\mathbb{N}$ and so by well-ordering, $B$ has a least element, say $\ell$. By the definition of $B$, for every $k\leq t<\ell, S(t)$ is true. The premise of the inductive hypothesis is true, and so $S(\ell)$ is true, contradicting that $\ell\in B$. Hence $B=\varnothing$. $\blacksquare$
Proof of weak induction from strong: Assume that strong induction holds (in particular, for $k=1$). That is, assume that if $S(1)$ is true and for every $m\geq 1, [S(1)\land S(2)\land\cdots\land S(m)]\to S(m+1)$, then for every $n\geq 1, S(n)$ is true.
Observe (by truth tables, if desired), that for $m+1$ statements $p_i$, $$ [p_1\to p_2]\land[p_2\to p_3]\land\cdots\land[p_m\to p_{m+1}]\Rightarrow[(p_1\land p_2\land\cdots\land p_m)\to p_{m+1}],\tag{$\dagger$} $$ itself a result provable by induction (see end of answer for such a proof).
Assume that the hypotheses of weak induction are true, that is, that $S(1)$ is true, and that for arbitrary $t, S(t)\to S(t+1)$. By repeated application of these recent assumptions, $S(1)\to S(2), S(2)\to S(3),\ldots, S(m)\to S(m+1)$ each hold. By the above observation, then $$ [S(1)\land S(2)\land\cdots\land S(m)]\to S(m+1). $$ Thus the hypotheses of strong induction are complete, and so one concludes that for every $n\geq 1$, the statement $S(n)$ is true, the consequence desired to complete the proof of weak induction. $\blacksquare$
Proving any positive integer $n\geq 2$ is a product of primes using strong induction: Let $S(n)$ be the statement "$n$ is a product of primes."
Base step ($n=2$): Since $n=2$ is trivially a product of primes (actually one prime, really), $S(2)$ is true.
Inductive step: Fix some $m\geq 2$, and assume that for every $t$ satisfying $2\leq t\leq m$, the statement $S(t)$ is true. To be shown is that $$ S(m+1) : m+1 \text{ is a product of primes}, $$ is true. If $m+1$ is a prime, then $S(m+1)$ is true. If $m+1$ is not prime, then there exist $r$ and $s$ with $2\leq r\leq m$ and $2\leq s\leq m$ so that $m+1=rs$. Since $S(r)$ is assumed to be true, $r$ is a product of primes [note: This is where it is imperative that we use strong induction; using weak induction, we cannot assume $S(r)$ is true]; similarly, by $S(s), s$ is a product of primes. Hence $m+1=rs$ is a product of primes, and so $S(m+1)$ holds. Thus, in either case, $S(m+1)$ holds, completing the inductive step.
By mathematical induction, for all $n\geq 2$, the statement $S(n)$ is true. $\blacksquare$
Proof of $1+2+3+\cdots+n = \frac{n(n+1)}{2}$ by strong induction: Using strong induction here is completely unnecessary, for you do not need it at all, and it is only likely to confuse people as to why you are using it. It will proceed just like a proof by weak induction, but the assumption at the outset will look different; nonetheless, just to show what I am talking about, I will prove it using strong induction.
Let $S(n)$ denote the proposition $$ S(n) : 1+2+3+\cdots+n = \frac{n(n+1)}{2}. $$
Base step ($n=1$): $S(1)$ is true because $1=\frac{1(1+1)}{2}$.
Inductive step: Fix some $k\geq 1$, and assume that for every $t$ satisfying $1\leq t\leq k$, the statement $S(t)$ is true. To be shown is that $$ S(k+1) : 1+2+3+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2} $$ follows. Beginning with the left-hand side of $S(k+1)$, \begin{align} \text{LHS} &= 1+2+3+\cdots+k+(k+1)\tag{by definition}\\[1em] &= (1+2+3+\cdots+k)+(k+1)\tag{group terms}\\[1em] &= \frac{k(k+1)}{2}+(k+1)\tag{by $S(k)$}\\[1em] &= (k+1)\left(\frac{k}{2}+1\right)\tag{factor out $k+1$}\\[1em] &= (k+1)\left(\frac{k+2}{2}\right)\tag{common denominator}\\[1em] &= \frac{(k+1)(k+2)}{2}\tag{desired expression}\\[1em] &= \text{RHS}, \end{align} we obtain the right-hand side of $S(k+1)$.
By mathematical induction, for all $n\geq 1$, the statement $S(n)$ is true. $\blacksquare$
$\color{red}{\text{Comment:}}$ See how this was really no different than how a proof by weak induction would work? The only thing different is really an unnecessary assumption made at the beginning of the proof. However, in your prime number proof, strong induction is essential; otherwise, we cannot assume $S(r)$ or $S(s)$ to be true. Here, any assumption regarding $t$ where $1\leq t\leq k$ is really useless because we don't actually use it anywhere in the proof, whereas we did use the assumptions $S(r)$ and $S(s)$ in the prime number proof, where $1\leq t\leq m$, because $r,s < m$. Does it now make sense why it was necessary to use strong induction in the prime number proof?
Proof of $(\dagger)$ by induction: For statements $p_1,\ldots,p_{m+1}$, we have that $$ [p_1\to p_2]\land[p_2\to p_3]\land\cdots\land[p_m\to p_{m+1}]\Rightarrow[(p_1\land p_2\land\cdots\land p_m)\to p_{m+1}]. $$
Proof. For each $m\in\mathbb{Z^+}$, let $S(m)$ be the statement that for $m+1$ statements $p_i$, $$ S(m) : [p_1\to p_2]\land[p_2\to p_3]\land\cdots\land[p_m\to p_{m+1}]\Rightarrow[(p_1\land p_2\land\cdots\land p_m)\to p_{m+1}]. $$ Base step: The statement $S(1)$ says $$ [p_1\to p_2]\Rightarrow [(p_1\land p_2)\to p_2], $$ which is true (since the right side is a tautology).
Inductive step: Fix $k\geq 1$, and assume that for any statements $q_1,\ldots,q_{k+1}$, both $$ S(1) : [q_1\to q_2]\Rightarrow [(q_1\land q_2)\to q_2] $$ and $$ S(k) : [q_1\to q_2]\land[q_2\to q_3]\land\cdots\land[q_k\to q_{k+1}]\Rightarrow[(q_1\land q_2\land\cdots\land q_k)\to q_{k+1}]. $$ hold. It remains to show that for any statements $p_1,p_2,\ldots,p_k,p_{k+1},p_{k+2}$ that $$ S(k+1) : [p_1\to p_2]\land[p_2\to p_3]\land\cdots\land[p_{k+1}\to p_{k+2}]\Rightarrow[(p_1\land p_2\land\cdots\land p_{k+1})\to p_{k+2}] $$ follows. Beginning with the left-hand side of $S(k+1)$, \begin{align} \text{LHS} &\equiv [p_1\to p_2]\land\cdots\land[p_{k+1}\to p_{k+2}]\land[p_{k+1}\to p_{k+2}]\\[0.5em] &\Downarrow\qquad \text{(definition of conjunction)}\\[0.5em] &[[p_1\to p_2]\land[p_2\to p_3]\land\cdots\land[p_{k+1}\to p_{k+2}]]\land[p_{k+1}\to p_{k+2}]\\[0.5em] &\Downarrow\qquad \text{(by $S(k)$ with each $q_i = p_i$)}\\[0.5em] &[(p_1\land p_2\land\cdots\land p_k)\to p_{k+1}]\land[p_{k+1}\to p_{k+2}]\\[0.5em] &\Downarrow\qquad \text{(by $S(1)$ with $q_1=p_1\land\cdots\land p_k)$ and $q_2=p_{k+1}$)}\\[0.5em] &[[(p_1\land p_2\land\cdots\land p_k)\land p_{k+1}]\to p_{k+1}]\land [p_{k+1}\to p_{k+2}]\\[0.5em] &\Downarrow\qquad \text{(by definition of conjunction)}\\[0.5em] &[(p_1\land p_2\land\cdots\land p_k\land p_{k+1}]\to p_{k+1}]\land [p_{k+1}\to p_{k+2}]\\[0.5em] &\Downarrow\qquad \text{(since $a\land b\to b$ with $b=[p_{k+1}\to p_{k+2}]$)}\\[0.5em] &[(p_1\land p_2\land\cdots\land p_k\land p_{k+1})\to p_{k+2}]\land[p_{k+1}\to p_{k+2}]\\[0.5em] &\Downarrow\qquad \text{(since $a\land b\to a$)}\\[0.5em] &(p_1\land p_2\land\cdots\land p_k\land p_{k+1})\to p_{k+2}\\[0.5em] &\equiv \text{RHS}, \end{align} we obtain the right-hand side of $S(k+1)$, which completes the inductive step.
By mathematical induction, for each $n\geq 1, S(n)$ holds. $\blacksquare$