Okay, got it.

First of all, your base case is n=1, as the definition is given for the natural numbers*. That's easy to check - write it out and you get 1 - 1 = 0. Also, before this gets to crazy, the goal is to show that the n+1 case is in fact the n case

*twice*, and is thus equal to 0+0

Now, assume that the statement

holds for 1 to n**. Then write out for n+1:

Apply the identity

to all terms of the sum, except the first and the last:

Reduce

to

and

to

. Also multiply in the

terms:

Reorder: for all of the pairs on the form

, group the left hand and right hand terms with the other left hand and right hand terms:

Extract the -1 from the left grouping, and turn the left and right grouping into sums:

Now, the right hand sum is only missing the k=0 term to be equal to 0 (by the original assumption). But the k=0 term is, as we saw as a part of the base proof, 1, so we can add the right hand sum and the 1, and get 0. We remove those two, and are left with:

The left hand sum can be simplified a lot, using the original assumption:

Meaning that:

So, the assumption for the sum being equal to 0 at n lead to the sum being equal to 0 at n+1, and the proof is done. Wow that got really fucking long. It sounded a lot easier in my head.

* Some definitions of the natural numbers include 0, but since the notes you have make specific mention of it when they want 0 included (with the subscript 0), that's not the case here

** n should not be used here, but from your examples it seems like you've learned that for induction, so I'll not go into the idiocy of some text books and lecturers of insisting that calling the general case n, and assuming n as a part of your proof makes sense by

*having two different variables named n aaaaaahrg*