Let $S_{n}=1^{3}+\cdots+n^{3}$ and construct the multiplication table:

| $\times$ | 1 | 2 | 3 | 4 | $\cdots$ |
| :---: | :---: | :---: | :---: | :---: | :---: |
| 1 | 1 | 2 | 3 | 4 | $\cdots$ |
| 2 | 2 | 4 | 6 | 8 | $\cdots$ |
| 3 | 3 | 6 | 9 | 12 | $\cdots$ |
| 4 | 4 | 8 | 12 | 16 | $\cdots$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ |

We define $\forall k \in \mathbb{N}^{*} I_{k}=\left\{(i, j) \in \mathbb{N}^{* 2}, \max (i, j)=k\right\}$ and $\forall k \in \mathbb{N}^{*} M_{k}=\sum_{i \in I_{k}} i$

In simpler terms, $M_{k}$ is simply the sum of the elements with indices $I_{k}$, refer to the coloring above.

Example: $M_{1}=1, M_{2}=2+4+2, M_{3}=3+6+9+6+3, M_{4}=4+8+12+16+12+8+4$ etc

1. Find a formula for $M_{k}$ and then prove it by induction.
2. Deduce the value of $S_{n}$.
1. We can find a formula for $M_{k}$ in several ways, let's start with one based on induction:

$M_{1}=1, M_{2}=2+4+2=8, M_{3}=27, M_{4}=64$. It seems logical to predict that $M_{k}=k^{3}$, let's prove this by induction.

Initialization: $M_{1}=1^{3}$ is correct.

Hereditary: Let $k \in \mathbb{N}^{*}$ such that $M_{k}=k^{3}$. Notice that to shift the right part of $I_{k}$ to the right by one step, it suffices to multiply it by $\frac{k+1}{k}$, similarly for the lower part and the one that follows.

However, the term at the bottom right appears only once in $M_{k}$, and thus $\frac{k+1}{k} M_{k}$ finally corresponds to all the terms in $M_{k+1}$ except the one at the bottom right and one of the two adjacent terms.

An example might be clearer: take $k=3$. The right block is 3, 6, and 9. Similarly for the bottom block.

If we multiply by $\frac{k+1}{k}=\frac{4}{3}$ this block, we get 4, 8, and 12, which is the right translation of this block.

For the bottom block, we need to remove the last term $\left(k^{2}=9\right)$ as it is already counted in the right block. So, 3 and 6 remain.

By still multiplying by $\frac{k+1}{k}=\frac{4}{3}$, we get the translation below 4 and 8.

Thus, $\frac{k+1}{k} M_{k}$ covers all indices except $(k+1, k+1)$ and one of the two adjacent, for example $(k+1, k)$.

We obtain that:

$$
\begin{gathered}
M_{k+1}=\frac{k+1}{k} \cdot M_{k}+(k+1)^{2}+k(k+1) \underset{H \cdot R \cdot}{=} k^{3} \cdot \frac{k+1}{k}+(k+1)^{2}+k(k+1)=(k+1)\left(k^{2}+k+1+k\right) \\
=(k+1)\left(k^{2}+2 k+1\right)=(k+1)^{3}
\end{gathered}
$$

We thus obtain the result by induction.

For a method without induction, notice that $M_{k}$ is the difference between the sum in the entire block of size $k$ and that of size $k-1$, and thus

$$
M_{k}=\sum_{i=1}^{k} \sum_{j=1}^{k} i j-\sum_{i=1}^{k-1} \sum_{j=1}^{k-1} i j=\left(\sum_{i=1}^{k} i\right)\left(\sum_{j=1}^{k} j\right)-\left(\sum_{i=1}^{k-1} i\right)\left(\sum_{j=1}^{k-1} j\right)=\left(\frac{k(k+1)}{2}\right)^{2}-\left(\frac{k(k-1)}{2}\right)^{2}
$$

$$
=\left(\frac{k}{2}\right)^{2}\left((k+1)^{2}-(k-1)^{2}\right)=\left(\frac{k}{2}\right)^{2}(4 k)=k^{3}
$$

Let's add one last method: $M_{k}$ is twice the sum of one of the blocks on the right or at the bottom minus the block at the bottom right as it is common to both. In other words:

$$
M_{k}=2 k \cdot(1+2+\cdots+k)-k^{2}=2 \cdot k \frac{k(k+1)}{2}-k^{2}=k^{3}
$$

2. In any case, $S_{n}=M_{1}+\cdots+M_{n}$ and this is simply the sum in the entire square of size $n$. Thus

$$
S_{n}=\sum_{i=1}^{n} \sum_{j=1}^{n} i j=\left(\sum_{i=1}^{n} i\right)\left(\sum_{j=1}^{n} j\right)=(1+\cdots+n)^{2}
$$