Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

enter image description here
Example of a proof of a theorem using weak(ordinary) induction
enter image description here enter image description here
The two types of inductions have process of proving P(a) and "for all integers $n \ge b, P(n)$" as a result in common.

For example, in the proof of the following question, we can use weak induction instead of strong induction, and using weak(ordinary) induction makes the proof simpler and shorter than the strong form of induction. So what's the benefit of using strong induction when it's replaceable by weak induction?

enter image description here

enter image description here

[EDIT] As requested, here's the weak induction version of the question. Plus, I changed the $s{k_1}$ part in red in the weak induction after reading answers. I now understand using weak induction doesn't prove the statement.

enter image description here

Source: Discrete Mathematics with Applications, Susanna S. Epp

share|cite|improve this question
3  
Do you mind spelling out the weak induction proof you have in mind? I can't figure it out from your clip notes. – Git Gud Feb 28 at 8:55
    
@GitGud I added my thoughts in gray and red in the proof. Did you see it? – buzzee Feb 28 at 8:58
    
Yes,I had read them. – Git Gud Feb 28 at 8:59
    
@GitGud I uploaded the weak induction proof of the question. – buzzee Feb 28 at 11:56
2  
@buzzee: read my answer. the reason you can't just change the words "strong" to "weak" is that the strong proof uses the assumption $s_{k-1}=5^{k-1}-1$. you don't have this assumption in the weak setting. but you do have it in the strong setting. – symplectomorphic Feb 28 at 12:43
up vote 8 down vote accepted

The other two answers are of course correct, but given your comments on Brian's answer, I will give a more down-to-earth response: in all likelihood, the proof you have in mind using weak induction is not correct. You should do as Git Gud says and spell out exactly what alternative proof you have in mind.

Why do I suspect you don't have a weak proof of the claim Epp proves? Because, as Brian illustrates, if you take $P(n)$ to be the statement $$s_n=5^n-1$$ you can't show $P(k+1)$ solely on the basis of $P(k)$.

Why? Just try it. By definition, $$s_{k+1}=6s_k-5s_{k-1}$$ and by the hypothesis $P(k)$, we can substitute $5^k-1$ for $s_k$, so we have $$s_{k+1}=6(5^k-1)-5\color{blue}{s_{k-1}}$$ But what do we do with $s_{k-1}$? We don't have any hypothesis on it! Only if we use strong induction can we use the hypothesis $P(k-1)$ and thereby substitute in $5^{k-1}-1$ for $s_{k-1}$.

share|cite|improve this answer
    
Good example but one could reason like that: since strong and weak induction are (provably) equivalent, there cannot be a statement that can be proved by one of them and not by the other. How is it possible? – Marco Disce Feb 28 at 12:12
    
@MarcoDisce See Brian's answer, specifically what I quote in my first comment to it. – Git Gud Feb 28 at 12:39
5  
@MarcoDisce: as Git Gud says, the fact that weak and strong induction are logically equivalent does not mean that weak induction can prove $P(k+1)$ solely on the basis of $P(k)$. You need a different $P(n)$ altogether. – symplectomorphic Feb 28 at 12:40

In the example that you’re discussing, you can not leave out proving $P(1)$. To see this, change the definition of the sequence slightly: $s_0=0$, $s_1=5$, and $s_k=6s_{k-1}-5s_{k-2}$ for $k\ge 2$. As before, let $P(n)$ be the formula $s_n=5^n-1$. Then $P(0)$ is true, and the induction step proceeds exactly as before to show that if $P(i)$ is true for all integers $i$ from $0$ through $k$, and $k\ge 1$, then $P(k+1)$ is true: there is nothing in that part of the argument that depends on the value of $s_1$. However, it is obviously not the case that $P(n)$ is true for all integers $n\ge 0$, since $P(1)$ is false.

The induction step requires knowing that $P(k)$ and $P(k-1)$ are true: without both of those, you cannot derive the truth of $P(k+1)$. And that means that to get $P(2)$, you need to know not only that $P(0)$ is true, but also that $P(1)$ is true. Thus, this argument really does use strong induction.

In fact the two forms of induction are logically equivalent, and every argument using strong induction can be converted to one that uses ordinary induction, but the conversion requires changing the proposition $P$. I can’t remember whether Epp proves the equivalence; if she does not, leave a question, and I’ll explain further.

In practice one simply uses whatever form of induction is convenient. I really wish that elementary texts didn’t make such a big deal of the difference: it’s not really very important, apart from the fact that so-called strong induction is in many ways a better introduction to more sophisticated forms of induction like structural and transfinite induction.

share|cite|improve this answer
1  
"The conversion requires changing the proposition $P$".This, I suspect, is what the OP is missing. Can't be sure because I don't really understand what weak induction proof the OP has in mind. – Git Gud Feb 28 at 8:58
    
@GitGud: I think that the OP simply didn’t realize that the argument presented by Epp actually is using strong induction in a way that is essential in the form in which the argument is presented. As I read it, the OP thought that checking the truth of $P(1)$ and using the truth of more than just $P(k)$ to get that of $P(k+1)$ were unnecessary in the argument as presented. (I could, however, be doing the OP an injustice.) – Brian M. Scott Feb 28 at 9:00
    
In your answer, "Then $P(0)$ is true, and the induction step proceeds exactly as before to show that if $P(i)$ is true for all integers $i$ from $0$ through $k$, and $k\ge 1$" Since only "$P(0)$ is true" and there's no '$P(1)$ is true' in that basis step part, it should be $k\ge 0$, not $k\ge 1$ in the induction step. – buzzee Feb 28 at 9:42
    
@buzzee: No, it should not: the induction step as given requires that both $P(k)$ and $P(k-1)$ be true, so starting at $k=0$ makes no sense. If the induction step required only that $P(k)$ be true, I could write ‘and $k\ge 0$, but that’s not the case, so I can’t. And that is why this really is an example of strong induction. – Brian M. Scott Feb 28 at 9:51
    
In the given proof, k is the upper limit range of the i. The induction step supposes ∀0≤i≤k, P(i) and then proves p(k+1). In this case, if k=0 we can't suppose P(k-1)=P(-1) be true, which is a counterexample to your claim that the given step requires both P(k) and P(k-1) be true. – buzzee Feb 28 at 10:18

Strong Induction is more intuitive in settings where one does not know in advance for which value one will need the induction hypothesis.

Consider the claim:

Every integer $n \ge 2$ is divisible by a prime number.

Using strong induction the proof is straightforward. It is true for $n=2$, as $2 \mid 2$ and $2$ is prime.

Assume the statement true for $2 \le a \le n$. We show $n+1$ is divisible by a prime number.

If $n+1$ is a prime number, then as $(n+1) \mid (n+1)$, the claim is proved. If $n+1$ is not a prime number then there exists some proper divisor $a\mid (n+1)$, so $2 \le a \le n$.

By induction hypothesis, we know that $a$ is divisible by a prime number $p$. Since $p \mid a $ and $a \mid (n+1)$ it follows that $p \mid (n+1)$ and the proof is complete.

If you want to do this with weak induction you will have to change the statement you want to prove to something less intuitive.

share|cite|improve this answer

Often it's conceptually easier to think about an argument in terms of strong induction. It is true that you can always recast the proof in terms of weak induction (though I don't exactly follow the comments you're making on the example in the question--what you have to do to make the argument use weak induction is change the statement you are proving by induction from "$P(k)$" to "$P(i)$ is true for all $i\leq k$"), but it is a bit simpler to use strong induction directly. I could turn your question around and ask you: why should you ever use weak induction, when it's replaceable by strong induction? It's largely a matter of taste, and which version leads to a more easily understood proof for the particular problem you are trying to solve.

Besides that, the concept of strong induction generalizes better than weak induction. Strong induction works on any well-ordered set (or even more generally, any set equipped with a well-founded relation). This generalized form of induction, called transfinite induction, is extremely important in set theory and also has applications in many other areas of mathematics, and cannot be reduced to weak induction the same way ordinary induction can. (Well, there is sort of a "weak induction" version of transfinite induction given by splitting into successor and limit cases, but it is still rather different from ordinary weak induction because of the limit cases besides $0$. And this doesn't work at all when doing induction on general well-founded relations.)

share|cite|improve this answer
    
I know "well-ordering principle", but haven't heard or read about "well-ordered set" before. – buzzee Feb 28 at 9:03
    
Does "well-ordered set" mean nonempty subsets in the following explanation? "Well-Ordering Principle. Every nonempty subset of the positive integers has a smallest element." sites.millersville.edu/bikenaga/math-proof/induction/… – buzzee Feb 28 at 10:21
1  
"Well-ordered set" refers to any set (not necessarily a subset of $\mathbb{N})$) with an ordering which satisfies the well-ordering principle. See en.wikipedia.org/wiki/Well-order. – Eric Wofsey Feb 28 at 19:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.