N+2 |   |
å | i = (N-1)(N+6)/2, N>=2 |
i=4 |   |
Sum(i=4,N+2)i = (N-1)(N+6)/2, N>=2.
Now on with the proof.
Base case: N=2. Plugging in 2 for N, we get
Sum(i=4,4)i = (2-1)(2+6)/2 => 4= 4 (show work!).
Inductive Step: (Show that if P(k) is true then P(k+1) must be true.) That is, show that
if Sum(i=4,k+2)i = (k-1)(k+6)/2 (inductive hypothesis) then Sum(i=4,k+3)i = (k)(k+7)/2 (just like above but k+1 for k)Proof of the inductive step: By the inductive hypothesis we know that Sum(i=4,k+2)i = (k-1)(k+6)/2. How can we use this (remember, we get to assume that the inductive hypothesis is true), to show that the k+1 case is true? Consider these points:
The sum goes to k+3 instead of k+2
Sum(i=4,k+2)i + (k+3) = (k-1)(k+6)/2 + k+3 (** note that Sum(i=4,k+2)i + (k+3) = Sum(i=4,k+3)i **)
We know that this is true because we got it by adding the same thing to both sides of an equation that we know is true (the inductive hypothesis). The LHS of this is the same as the k+1 case; simplify the RHS and see if it is the same as the RHS of the k+1 case. SHOW YOUR WORK!
(k-1)(k+6)/2 + k+3 = (k-1)(k+6)/2 + 2(k+3)/2 = (k2 + 5K-6+2k+6)/2 = (k2 + 7K)/2 = k(k+7)/2 .
We have now shown that P(k)->P(k+1), so the proof is complete.