I am having trouble understanding how to prove that the sum of the first $n$ positive even integers is $n^2 + n$ using strong induction.

Question

Show the sum of the first $n$ positive even integers is $n^2 + n$ using strong induction.

I can't solve the above problem using strong induction. It will be very helpful if I can get the solution. Thanks in advance.

Answer 1

Basic case is trivially true.

Now assume the sum of the first k positive even integers is $k^2+k$ for all values $1,2,...k_0$

Then we know that the $(k_0+1)^{th}$ even integer is $2k_0+2$, summing that with the first $k_0$ positive even integers yields $k_0^2+3k_0+2=(k_0+1)^2+(k_0+1)$

By the principles of strong induction, the formula is correct. However, strong induction is not necessary in this case as you can easily derive this formula with a summation.

Answer 2

The case $n=1$ is obviously true.

Suppose that, for some $n$, we have that $\displaystyle\sum_{i=1}^{k} 2i = k^2+k$ for all $k\le n$.

Then, for any $k\le n$:

$\displaystyle\sum_{i=1}^{n+1} 2i = \displaystyle\sum_{i=1}^{k} 2i + \displaystyle\sum_{i=k+1}^{n+1} 2i = \displaystyle\sum_{i=1}^{k} 2i + \displaystyle\sum_{i=1}^{n+1-k} 2(i+k) = \\ \displaystyle\sum_{i=1}^{k} 2i + \displaystyle\sum_{i=1}^{n+1-k} 2i + \displaystyle\sum_{i=1}^{n+1-k} 2k = (k^2+k) + \left( (n+1-k)^2 + n+1-k \right) + 2k(n+1-k) = \\ k^2+k + (n+1)^2-2kn-2k+k^2+(n+1)-k+2kn+2k-2k^2 = \\ (n+1)^2+(n+1) $

So, by induction, this holds for any $n\in\mathbb{N}$