Calculate $(k+1)^{3}-k^{3}$ then find the formula for $\sum_{k=1}^{n} k^{2}$.

## Other Counting Tools

Example 3. There are $d^{n}$ different rolls of $\mathrm{n}$ colored dice with $\mathrm{d}$ faces.
On a :

$$
(k+1)^{3}-k^{3}=3 k^{2}+3 k+1
$$

Idea: telescoping sum. We have:

$$
\begin{aligned}
& \sum_{k=1}^{n}(k+1)^{3}-k^{3}=\sum_{k=1}^{n} 3 k^{2}+3 k+1 \\
& \sum_{k=1}^{n}(k+1)^{3}-k^{3}=(n+1)^{3}-1
\end{aligned}
$$

Therefore

$$
\sum_{k=1}^{n} k^{2}=\frac{(n+1)^{3}-1-\sum_{k=1}^{n} 3 k+1}{3}=\cdots=\frac{n(n+1)(2 n+1)}{6}
$$