# Proof:Σi = n(n+1)/2

Proof:
We prove this statement by weak induction on . Let

be the statement "". We will show and (assuming ).

Aside: Note that does not include the "for all n". To see why, imagine that it did. Then would say "for all 7, ...",
Aside: A common mistake people make when writing inductive proofs, especially those involving formulas, is to think of as a 'number' and not a statement. If you find yourself writing , you are doing something wrong! Plugging this in would give which doesn't make sense.

In the case where , the left hand side and the right hand side are both 0.

Now, to see , first assume . We want to show , i.e. that . We compute:

as required.

Aside: This proof uses a common pattern in inductive proofs (and in many other proofs too!): in the first few steps, we take what we want to show, and manipulate it so that we can use what we know ( in this case). If you get stuck, it's always good to look at what you've assumed already and try to find a way to apply it.