### Fill-In-The-Blank Proof By Induction

Fill in the blanks in the inductive proof below of the following property P(N):
 N+2 å i = (N-1)(N+6)/2, N>=2 i=4
For ease of formatting I will write this as follows:

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 left hand side (LHS) of the k+1 case is different from the left hand side of the inductive hypothesis (the k case) in just one way:

The sum goes to k+3 instead of k+2

• To make the LHS of the inductive hypothesis the same as the LHS of the k+1 case, you would have to add  k+3  to it. Adding this to both sides of the inductive hypothesis gives

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.