Showing that $\sum_{j=0}^n (j+1) =\frac{(n+1) (n+2)}{2}$ whenever $n$ is a nonnegative integer.

Question

First of all this is a mathematical induction proof. I faced difficulties just with the step 1 when verifying that $P(1)$ is true. Where $n=1$, the L.H.S is $$\sum_{j=0}^n (j+1)=0+1=1$$

Here I faced trouble when trying to prove the right hand side.

By the way, is my left hand side proof correct? How can I prove the R.H.S.?

Answer 1

Here is the main part of the inductive step: \begin{align} \sum_{i=0}^{k+1}(i+1)&= \sum_{i=0}^k(i+1)+(k+2)\tag{by definition}\\[1em] &= \frac{(k+1)(k+2)}{2}+(k+2)\tag{by inductive hyp.}\\[1em] &= \frac{(k+1)(k+2)+2(k+2)}{2}\tag{common denom.}\\[1em] &= \frac{(k+2)(k+1+2)}{2}\tag{factor out $(k+2)$}\\[1em] &= \frac{(k+2)(k+3)}{2}.\tag{simplify} \end{align}

Answer 2

So how induction works is that we first need to prove our base case. In this problem the base case is $n=1$. The $n=1$ base case yields $\sum_{j=o}^1 (j+1) = (0+1)+(1+1) = 3 = \frac{(1+1)(1+2)}{2}$. So this proves the base case since the answer to $\sum_{j=o}^1 (j+1)$ is of the form $\frac{(n+1)(n+2)}{2}$.

We now make our assumption (the inductive hypothesis). In my proof I assumed it to be true for $n=(k-1)$ and then proved it to be true for $n=k$. In Daniels proof above he assumed it to be true for $n=k$ and then proved it to be true for $n=(k+1)$. Both ways are fine and in this case neither one is harder than the other.

So, assume the statement is true for $n = (k-1) $ for an integer $k$ which means $\sum_{j=o}^{k-1} (j+1) =\frac{((k-1)+1)((k-1)+2)}{2} = \frac{k(k+1)}{2}$ and we are going to use this to show true for $n = k$ by noting that $\sum_{j=o}^k (j+1) = \sum_{j=o}^{k-1} (j+1) + (k+1) $. What we did here was we wrote the last term in the sum separately and this allows us to use our inductive hypothesis in the following way:

Since we already know that $ \sum_{j=o}^{k-1} (j+1) = \frac{k(k+1)}{2}$ from the inductive hypothesis then $\begin{align} \sum_{j=o}^k (j+1) &= \sum_{j=o}^{k-1} (j+1) + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \\ & =\frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\ &= \frac{(k+1)(k+2)}{2} \end{align}$

And this is what we wanted to show.