Timeline for Strong induction without a base case
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 21, 2010 at 19:10 | comment | added | Joel David Hamkins | @Ravi: Yes, I thought that is what you had had in mind. My point was that your defining recurrence formula simplifies in one step to S(n+1)=S(n)+S(n), which avoids the series and seems naturally treated with weak induction. | |
| Jan 21, 2010 at 13:59 | comment | added | Ravi Boppana | Here is the proof by strong induction I had in mind. Suppose by strong induction that $S(k) = 2^k$ for all $k < n$. Then $S(n) = 1 + \sum_{k=0}^{n-1} S(k) = 1 + \sum_{k=0}^{n-1} 2^k = 1 + (2^n - 1) = 2^n$. (The third equation is using the usual formula for geometric series.) The proof seems to be using strong induction, not weak induction. I don't think I needed to handle n = 0 separately. If you'd rather avoid the appeal to the formula for geometric series, then the examples in my other answer might be better. | |
| Jan 21, 2010 at 13:19 | comment | added | Joel David Hamkins | This doesn't seem to be the kind of example that was requested. First, the argument here seems more naturally carried out with (weak) induction, rather than strong induction, since the induction appeals to the immediately preceding case. Secondly, the nature of the argument at n=0, even if you do it with strong induction, is not the same as for other n, so it treats what amounts to the base case differently. | |
| Jan 19, 2010 at 3:04 | history | answered | Ravi Boppana | CC BY-SA 2.5 |