Let $n$ be a natural number. Give an explicit formula for the sum $0+1+$ $2+\ldots+n$.

Hint. Try a formula of the type: $0+1+2+\ldots+n=a n^{2}+b n+c$, where $a, b, c$ are three constants.
As is often the case when dealing with recurrence, we will proceed in two steps: first, we conjecture an explicit formula using small values of $n$, then we show that it holds for all $n$.

If we denote $u_{n}:=0+1+\ldots+(n-1)+n$ for all $n \in \mathbb{N}$, we have:

| $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $u_{n}$ | 0 | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 |

A priori, we can start by looking for $u_{n}$ as an affine function of $n$, i.e., $u_{n}=a n+b$ for all $n$, with $a, b$ fixed (in real life, we don't always have such indications...). We would then have $u_{0}=a \times 0+b=0$, hence $b=0$, and $u_{1}=a \times 1+0=1$, hence $a=1$. But $u_{2} \neq 1 \times 2+0$. So we need to try something else...

Next, we look for $u_{n}$ as a polynomial function of the second degree in $n$, i.e., $u_{n}=a n^{2}+b n+c$ for all $n$, with $a, b, c$ fixed. We would then have $u_{0}=$ $a \times 0^{2}+b \times 0+c=0$, hence $c=0$, and $u_{1}=a \times 1+b \times 1+0=1$, hence $a+b=1$, and $u_{2}=a \times 4+b \times 2+0=3$, hence $4 a+2 b=3$. We deduce $a=b=\frac{1}{2}$, which would give (if this is confirmed...) : $u_{n}=\frac{n^{2}+n}{2}=\frac{n(n+1)}{2}$.

Moreover, this formula is verified for all the values calculated in the table. We are therefore very motivated to show that $u_{n}=\frac{n(n+1)}{2}$ for all $n \in \mathbb{N}$, by induction.

The initialization for $n=0$ is already done (see the judicious choice of $a, b, c$).

Suppose now that there exists a natural number $n$ such that $u_{n}=\frac{n(n+1)}{2}$. Then:

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

so $\mathcal{P}_{n+1}$ is true, which concludes by the principle of induction.