Beginners Number Theory Problem
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 ?