Friday, October 24, 2008

PS3 - G(n) induction step

I got my third problem set back today, and I noticed that the marker made a note on my induction step. Here is the beginning of my proof by complete induction:

      Let P(n): G(n) = S(i from 0 to n) 3^i
Claim: for any natural number n, P(n)

Base case n=0: G(0) = 1 (by definition of G)
S(i from 0 to 0) 3^i = 3^0 = 1
Then P(0) holds.

Induction Step: Let n be part of N\{0} and assume P(0) /\ ... /\ P(n-1)


The marker asked why can't n=0 be in the induction step? They mentioned that I need this, but then wouldn't P(n-1) = P(-1) for n=0? The claim was only about P being true for natural numbers, so I am a little confused. Indeed I needed n=0, but I specifically handled that in the base case.

No comments: