# Prove by induction (make sure to show the base case, the inductive hypothesis, and all steps in the proof) Sum (from k=1 to N) of k is less than N^2 for all N >= 2

## Answer to: Prove by induction (make sure to show the base case, the inductive hypothesis, and all steps in the proof) Sum (from k=1 to N) of k is less than N^2 for all N >= 2

Base case is N=2. Sum is 1+2=3. Is 3 < 2^2? 3 < 4? yes

Inductive hypothesis:

Lets assume an M such that Sum(from k=1 to M) of k < M^2, M > 2.

Now show that sum(k=1 to M+1) of k < (M+1)^2

sum(k=1 to M+1) of k is sum(k=1 to M) of k + (M+1)

Is sum(k=1 to M) of k + (M+1) < (M+1)^2 ?

Is sum(k=1 to M) of k + (M+1) < M^2 +2M +1?

By inductive hypo, we know sum(k=1 to M) of k < M^2

We also know that if a < b and c < d then a+c < b+d (rules of algebra)

So can we show that (M+1) < 2M + 1?

M < 2M ? yes if M > 0 and inductive hypo says M > 2