Solution to Prove by induction (make sure to show the base case, the inductive hypothesis, and all … - Sikademy

Nov. 27, 2020

Archangel Macsika Sikademy Image

Archangel Macsika

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