(Sum of cubes)

We construct a figure composed of $n$ nested crowns, as illustrated below, such that $\forall k \in\{1, \ldots, n\}$, the $k$-th crown is composed of $4 k$ squares of side length $k$.

Deduce a formula for the sum: $S_{n}=1^{3}+\ldots+n^{3}$.

![](https://cdn.mathpix.com/cropped/2024_05_10_346641170ac76390eef3g-070.jpg?height=1082&width=1079&top_left_y=558&top_left_x=494)
The area covered by the $k$-th ring is $A_{k}=4 k \times k^{2}=k^{3}$, so $4 \times S_{n}$ is the total area covered by the square of side $n(n+1)$, hence the formula:

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

## Remark 3.5.1.

This is the square of the sum of the first $n$ integers.

## - A bit of theory -

We distinguish a few principles in combinatorics, which can be useful in double counting. These concepts are quite intuitive, but it is useful to know them, as well as the associated vocabulary, for a clear writing in particular.

## Definition 3.5.2.

Let $E$ be a finite set. The cardinality of $E$, denoted $|E|$ or $\# E$, is the number of its elements.

A counting problem is always a search for the cardinality of a given set.

## Definition 3.5.3.

A partition of a set $E$ is a set of subsets of $E$ that are pairwise disjoint, and whose union is $E$. In other words, partitioning $E$ means distributing all its elements into "packets".

Thus, if we partition the set we wish to count, and we know how to count each of the parts of the partition, the sum of their cardinalities is equal to the cardinality of the initial set.

## Partition according to a function

Let $f$ be a function from a set $E$ to a set $F$ (to each element $x$ of $E$, we associate a unique element of $F$, called the image of $x$ by $f$ and denoted $f(x)$). For $y \in F$, we denote $f^{-1}(\{y\})$ the inverse image of $\{y\}$ by $f$, that is, the set of elements $x$ of $E$ such that $f(x)=y$ (set of antecedents of $y$). We can then partition $E$ according to the image of its elements:

$$
\left\{f^{-1}\{y\} \mid y \in F\right\}
$$

is a partition of $E$.

Lemma 3.5.4 (Shepherd's Lemma).

We want to count the elements of a finite set $F$ (the sheep in a flock). We assume that there exists a function $f: E \rightarrow F$ and an integer $p \leqslant 1$, such that $\forall y \in F, f^{-1}(y)$ has exactly $p$ elements (we count the number of legs, we know that exactly 4 belong to the same sheep). Then:

$$
|F|=\frac{|E|}{p}
$$

(the number of sheep is a quarter of the number of legs)

## Definition 3.5.5.

Let $f: E \rightarrow F$. We say that:

- $f$ is injective if two distinct elements of $E$ always have two distinct images by $f$. In other words, every element of $F$ has at most one antecedent by $f$ (it may have none).
- $f$ is surjective if all elements of $F$ have at least one antecedent by $f$.
- $f$ is bijective if it is both injective and surjective, that is, every element $y$ of $F$ has exactly one antecedent by $f$.

## Proposition 3.5.6.

Let $E$ and $F$ be two finite sets and $f: E \rightarrow F$.

- If $f$ is injective, then $|E| \leqslant|F|$.
- If $f$ is surjective, then $|E| \geqslant|F|$.
- If $f$ is bijective, then $|E|=|F|$.

Thus, in double counting, we are interested in bijections: if we know the cardinality of a set in bijection with the set we want to count, we have solved our problem. It is therefore a matter of finding a suitable bijection and a set that is "easy to count".

## Definition 3.5.7.

A permutation of a finite set $E$ is a bijective function $\sigma$ from $E$ to itself. For $n \in \mathbb{N}$, we denote $S_{n}$ the set of permutations of $\{1, \ldots, n\}$.

## Definition 3.5.8.

Let $E$ and $F$ be two sets. The Cartesian product of $E$ and $F$, denoted $E \times F$, is the set of pairs $(x, y)$ where $x \in E$ and $y \in F$.

## Proposition 3.5.9.

$|E \times F|=|E| \times|F|$.

To count a set, we can thus view it as the Cartesian product of other sets that we know better, and deduce its cardinality.