Precise Statement of Strong Induction

50 Views Asked by At

I am a TA for a CS course and on an exam I was grading I had a "strong" discussion with the professor that the answer was incorrect involving strong induction. His explanation of strong induction is this:

Given some property P over the natural numbers we want to prove P(n) is true.

1.  Let b be the base case and prove P(b) is true.
2.  The inductive hypothesis is to assume that for all i, b < i < n, P(i) is true.

I tried to argue that if you don't assume that P(i) is true when i equals b then you can't use it. He says it is pointless to assume it is true because you already proved it in step 1. I pointed out that multiple books state that they include b but he just waved it off and said they were sloppy.

Does it matter if you include the base case or not in the inductive hypothesis?

1

There are 1 best solutions below

0
On

Practically speaking, it doesn't matter much. You're allowed to use the fact that $P(b)$ is True whether or not you assume it, because you've proven it. Your professor is right that you don't have to assume it, and can only assume $P(i)$ for $b<i<n$. In that sense, it's more precise to not assume it for $b$. Personally I don't view the difference as particularly important and wouldn't have taken any points off.