In: Computer Science
Use induction to prove that 2 + 4 + 6 + ... + 2n = n2 + n for n ≥ 1.
Prove this theorem as it is given, i.e., don’t first simplify it algebraically to some other formula that you may recognize before starting the induction proof.
I'd appreciate if you could label the steps you take, Thank you!
Let f (n) -> 2 + 4 + 6+ …+2n = n2 + n
f (1) -> 2 = 12 + 1 = 2, which is true
Hence, f (1) is true.
Let us assume that f (n) is true for some natural number n = k where k >=1
∴ f (k)-> 2 + 4 + 6 + ….+2k = k2 + k ---------- (i)
Now, we have to prove that f (k + 1) is true.
f (k + 1) -> 2 + 4 + 6 + 8+ …..+2k + 2(k+1)
= k2 + k + 2(k+ 1) [Using (i)]
= k2 + k + 2k + 2
= k2 + 2k+1+k+1
= (k + 1)2 + k+ 1
Hence, f (k + 1) is true whenever f (k) is true.
So, by the principle of mathematical induction f (n) is true for any natural number n where n>=1.