Take the 2-minute tour ×
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.

I recently learned about strong induction, and had a couple questions. First, on sites such as this one: http://www.mathblog.dk/strong-induction/ , it is said that using strong induction requires more bases case. (This makes sense to me, as you are making a bigger claim) When I asked my professor, though, he said there are no more base cases needed. In this light, I don't see why anyone would ever go through the effort of even attempting 'weak' induction, as it is included in strong induction, and no extra steps of work are needed-only a larger assumption.

share|improve this question
    
OK.${{{{{}}}}}$ –  Git Gud Sep 4 '13 at 15:35
2  
You are right, strong induction covers everything. But often it is the case $k$ that yields the case $k+1$, with no help needed from cases $j\lt k$. So using weak induction helps us concentrate on the right thing. But there are cases of strong induction where multiple base cases are needed. –  André Nicolas Sep 4 '13 at 15:37
    
The link you gave doesn't say that you need more base cases in general, this just happens in the example. But this could happen with either form of induction. –  Matt Pressland Sep 4 '13 at 15:43

1 Answer 1

Strong induction is the following:

  1. Show that $p_0$ is true.
  2. Suppose that $p_1$, $\ldots$, $p_n$ is true and show that $p_{n+1}$ is true.
  3. Conclude that $p_i$ is true for all $i$

Weak induction is the following:

  1. Show that $p_0$ is true.
  2. Suppose that $p_n$ is true and show that $p_{n+1}$ is true.
  3. Conclude that $p_i$ is true for all $i$

Usually, it is considered more elegant to assume the least amount of things possible. So if you can finish your work by using only weak induction, it is preferred. As you pointed out, you could use strong induction instead of weak induction all the time.

share|improve this answer

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.