induction - Understanding the proof that the sum of the first $n$ natural numbers is $frac{1}{2}n(n+1)$

I'm reading the following book: http://www.cs.princeton.edu/courses/archive/spring10/cos433/mathcs.pdf.

In page 26, they attempt to prove the following theorem using Induction:

For all $n \in \mathbb{N}$:
$$1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$

In order to prove the theorem we need to prove the following statements:

• $P(0)$ is true.



• For all $n \in \mathbb{N}$, $P(n)$ implies $P(n + 1)$.

Proving the first one is easy:

$$P(0) = 0 = 0 * (0 + 1) / 2$$
$$= 0 = 0 * 1 / 2$$
$$= 0 = 0 / 2$$
$$= 0 = 0$$

In order to prove the second, they state the following:

$$1+2+\cdots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) \tag{1}$$
$$= \frac{(n+1)(n+2)}{2} \tag{2}$$

I don't understand how they get from (1) to (2) and how that proves that proves that for all $n \in \mathbb{N}$, $P(n)$ implies $P(n + 1)$ is true.

I'm clearly missing something in the process. Can someone clear the fog for me?

Answer

Just do the math.

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

For your second problem, note that you proved that $$1+2+\ldots+n+(n+1) = \frac{(n+2)(n+1)}{2}.$$

The initial statement is $1+2+\ldots+k = \frac{k(k+1)}{2}$, with another letter. If you do $k=n+1$ you will get $1+2+\ldots+(n+1) = \frac{(n+1)((n+1)+1)}{2} = \frac{(n+2)(n+1)}{2}$, and that is what you just proved.