### 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 =
(k__^{2} + 5K-6+2k+6)/2 = (k^{2} + 7K)/2 = k(k+7)/2 .

We have now shown that P(k)->P(k+1), so the proof is complete.