I just started reading about number theory and here was the first problem verbatim.

$\displaystyle SUM[j=0,n] {j} = n(n+1)/2 $

Remarks and Hints: A statement which is proved by induction often has an integral parameter,

such as n in our case. You then need to do two steps, either of which can be done first:

(1) You prove that the statement holds for the case n = 1, or whatever the first case is

that you’re interested in. This is called the base case.

(2) You prove that IF the statement holds for the case n = k, THEN it holds for the case

n = k + 1. This is called the inductive step.

Thus, for step 2, you get to ASSUME the statement for n = k, and show that this is enough

to imply it for n = k + 1. In your proof, indicate clearly when you’re doing the base case

and when you’re doing the inductive step.

So how do I prove this exactly? I know that if I sum j from 0 -> n where n=1 I'll get one, and i know for n=1 that n(n+1)/2 = 1(1+1)/2 = 1 so that makes it true, but what about for the inductive step? What do I do for n=k or n = k+1 ?