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:
Post a Comment