I just started to learn induction in my first year course. I'm having a difficult time grasping the concept. I believe I understand the basics but could someone summarize simple induction and strong induction and explain what the differences are? The video I'm watching explains that if $P(k)$ is true then $P(k+1)$ is true for simple induction, and for strong induction if $P(i)$ is true for all $i$ less than equal to $k$ then $P(k+1)$ is true. I don't really know what that means.
[Math] What’s the difference between simple induction and strong induction
induction
Related Solutions
I believe the crux of Noble's question, as presented in his recent comment, is:
[B]ut I can't see how assuming it's true for more than one value is more powerful.
In logical terms, we say that a statement $A$ is stronger than a statement $B$ if $A \implies B$. It is clear that -- forgive me for writing $\wedge$ for and when discussing logical statements --
$A \wedge A' \implies A$,
and more generally
$A_1 \wedge A_2 \wedge \ldots \wedge A_n \implies A_n$.
In other words, assuming a set of things is stronger than assuming a subset of things.
This is the sense in which strong induction is "stronger" than conventional induction: for your predicate $P$ indexed by the positive integers, assuming $P(1) \wedge \ldots \wedge P(n)$ is stronger than just assuming $P(n)$. In more practical terms, the more hypotheses you assume, the more you have to work with and it can only get easier to construct a proof.
Now let me supplement with further comments:
Nevertheless the principle of mathematical induction implies (and, more obviously, is implied by) the principle of strong induction, via the simple trick of switching from the predicate $P(n)$ to the predicate $Q(n) = P(1) \wedge \ldots P(n)$.
Here is a further possible source of confusion in the terminology. Suppose I have a theorem of the form $A \wedge B \implies C$. Someone else comes along and proves the theorem $A \implies C$. Now their theorem is stronger than mine: i.e., it implies my theorem. Thus when you weaken the hypotheses of an implication you strengthen the implication. (While we're here, let's mention that if you strengthen the conclusion of an implication, you strengthen the implication.) This apparent reversal may be the locus of the OP's confusion.
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
- (i) $S(k)$ holds, and
- (ii) for every $m\geq k, S(m)\to S(m+1)$,
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
- (i) $S(k)$ is true and
- (ii) for every $m\geq k, [S(k)\land S(k+1)\land\cdots\land S(m)]\to S(m+1)$,
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$
Best Answer
With simple induction you use "if $p(k)$ is true then $p(k+1)$ is true" while in strong induction you use "if $p(i)$ is true for all $i$ less than or equal to $k$ then $p(k+1)$ is true", where $p(k)$ is some statement depending on the positive integer $k$.
They are NOT "identical" but they are equivalent.
It is easy to see that if strong induction is true then simple induction is true: if you know that statement $p(i)$ is true for all $i$ less than or equal to $k$, then you know that it is true, in particular, for $i=k$ and can use simple induction.
It is harder to prove, but still true, that if strong induction is true, then simple induction is true. That is what we mean by "equivalent".
Here we have a question. It is not why we still have "weak" induction - it's why we still have "strong" induction when this is not actually any stronger.
My opinion is that the reason this distinction remains is that it serves a pedagogical purpose. The first proofs by induction that we teach are usually things like $\forall n\left[\sum_{i=0}^n i= \frac{n(n+1)}{2}\right]$. The proofs of these naturally suggest "weak" induction, which students learn as a pattern to mimic.
Later, we teach more difficult proofs where that pattern no longer works. To give a name to the difference, we call the new pattern "strong induction" so that we can distinguish between the methods when presenting a proof in lecture. Then we can tell a student "try using strong induction", which is more helpful than just "try using induction".