Proving a summation

Question

My exercise is to prove $\sum_{i=0}^n i = \frac{n(n+1)}{2} $. This is what I tried:

Let $P(n) = \sum_{i=0}^n i$

Step 1: Show $P(1)$ is true

$$P(1) = \sum_{i=0}^{1} i = 0 + 1 = 1$$

$$\frac{n(n + 1)}{2} = \frac{1(1 + 1)}{2} = \frac{2}{2} = 1\ \text{(true)}$$

Step 2: Show $P(n+1)$ is true; that is, show $\sum_{i=0}^{n+1} i = \frac{(n+1)(n+1+1)}{2} = \frac{n^2 + 3n + 2}{2}$

$$P(n+1) = \sum_{i=0}^{n+1} i = \sum_{i=0}^n i +(n+1)$$

This is where I got stuck. Is my process correct so far? How do I move foward?

Answer 1

You have a bit of a notation issue. Since $P(n)$ is a statement that is either true or false (and not a number, as your work seems to imply), we should instead define:

$$ P(n)~\colon \qquad \sum_{i=0}^n i = \frac{n(n+1)}{2} $$

Now to move forward, we want to apply the induction hypothesis [recall that Step 2 involves proving that $P(n) \implies P(n + 1)$]. Since we know that $P(n)$ is true, use the fact that: $$ \sum_{i=0}^n i = \frac{n(n+1)}{2} $$

Answer 2

I was able to figure it out thanks to Adriano. Here is the proof:

\begin{align*} P(n+1) = \sum_{i=0}^{n+1} i &= \sum_{i=0}^n i + (n+1)\\ &= \frac{n(n+1)}{2} + n+1\\ &= \frac{n(n+1)}{2} + \frac{2(n+1)}{2}\\ &= \frac{n(n+1)}{2} + \frac{2n+2}{2}\\ &= \frac{n(n+1) + 2n+2}{2}\\ &= \frac{n^2+n+2n+2}{2}\\ &= \frac{n^2+3n+2}{2}\ \text{(true)} \end{align*}

Therefore by the principle of mathematical induction $P(n)$ is true for all $n \geq 0$, that is $\sum_{k=0}^{n} i = \frac{n(n+1)}{2}$ for all $n \geq 0$.