Techniques — Sommes et Produits

def S(n):
    total = 0
    for k in range(1, n+1):
        total += k**2 + 2*k + n + 5
    return total  # dépend de n, pas de k

Solution — On applique l'algorithme avec \(j = n - k\) :

• Borne inf. : \(k = 0 \Rightarrow j = n\)
• Borne sup. : \(k = n \Rightarrow j = 0\)
• Terme général : \(k = n - j\), donc \(\binom{n}{k}x^k = \binom{n}{n-j}x^{n-j} = \binom{n}{j}x^{n-j}\)

Le retournement donne \(\displaystyle\sum_{j=n}^{0}\) — la borne du bas est plus grande que la borne du haut, ce qui est inhabituel. On renverse les bornes en invoquant la commutativité de l'addition : l'ordre dans lequel on additionne les termes ne change pas la somme. Donc \(\displaystyle\sum_{j=n}^{0} = \sum_{j=0}^{n}\) :

\[\sum_{k=0}^{n}\binom{n}{k}x^k = \sum_{j=0}^{n}\binom{n}{j}x^{n-j} = x^n\sum_{j=0}^{n}\binom{n}{j}\left(\frac{1}{x}\right)^j = x^n\!\left(1+\frac{1}{x}\right)^{\!n} = (x+1)^n\]

Résultat connu par le binôme de Newton — bon exercice de mécanique, mais pas de surprise.

Solution — 1. Le terme général contient \((n-k)\) — c'est le complémentaire de l'indice de sommation \(k\) par rapport à \(n\). On pose donc naturellement \(j = n - k\) pour que \((n-k)\) devienne simplement \(j\).

2. On applique l'algorithme avec \(j = n - k\) :

• Borne inf. : \(k = 0 \Rightarrow j = n\)
• Borne sup. : \(k = n \Rightarrow j = 0\)
• Terme général : \(k = n - j\), donc \((n-k)\binom{n}{k} = j\binom{n}{n-j} = j\binom{n}{j}\)

Le retournement donne \(\displaystyle\sum_{j=n}^{0}\) — on renverse les bornes par commutativité de l'addition :

\[\sum_{k=0}^{n}(n-k)\binom{n}{k} = \sum_{j=0}^{n}j\binom{n}{j}\]

Or \(j\binom{n}{j} = n\binom{n-1}{j-1}\), donc :

\[\sum_{j=0}^{n}j\binom{n}{j} = n\sum_{j=1}^{n}\binom{n-1}{j-1}\]

On observe que \(\binom{n-1}{j-1}\) a son indice décalé de 1 — exactement comme dans l'exemple du DM. On veut se ramener à \(\binom{n-1}{i}\) avec l'indice seul en bas.

On pose \(i = j - 1\) :

• Borne inf. : \(j = 1 \Rightarrow i = 0\)
• Borne sup. : \(j = n \Rightarrow i = n-1\)
• Terme général : \(\binom{n-1}{j-1} = \binom{n-1}{i}\)

On obtient donc :

\[n\sum_{j=1}^{n}\binom{n-1}{j-1} = n\sum_{i=0}^{n-1}\binom{n-1}{i}\]

Or par le binôme de Newton avec \(x = y = 1\) : \((1+1)^{n-1} = \displaystyle\sum_{i=0}^{n-1}\binom{n-1}{i} = 2^{n-1}\). Donc :

\[\sum_{k=0}^{n}(n-k)\binom{n}{k} = n \cdot 2^{n-1}\]

Le changement d'indice transforme une somme difficile en une somme connue — c'est l'intérêt de la méthode.

Solution — On applique le retournement \(j = n - k\) à \(S\) :

• Borne inf. : \(k = 0 \Rightarrow j = n\)
• Borne sup. : \(k = n \Rightarrow j = 0\)
• Terme général : \(k = n - j\)

Donc \(S = \displaystyle\sum_{j=0}^{n}(n-j) = \sum_{k=0}^{n}(n-k)\). On additionne les deux expressions de \(S\) :

\[2S = \sum_{k=0}^{n} k + \sum_{k=0}^{n}(n-k) = \sum_{k=0}^{n}\bigl(k + (n-k)\bigr) = \sum_{k=0}^{n} n = (n+1)\,n\]

D'où \(\displaystyle S = \frac{n(n+1)}{2}\).

C'est la démonstration classique de Gauss — le retournement donne une deuxième écriture de \(S\), et additionner les deux fait apparaître une somme triviale terme à terme.

Solution —

On reconnaît le pattern 1 : produit de termes consécutifs au dénominateur. On décompose en éléments simples :

\[\frac{1}{k(k+1)} = \frac{A}{k} + \frac{B}{k+1}\]

En réduisant : \(A(k+1) + Bk = 1\). Pour \(k=0\) : \(A = 1\). Pour \(k=-1\) : \(-B = 1\) donc \(B = -1\). Ainsi :

\[\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1} = v_k - v_{k+1}\]

avec \(v_k = \dfrac{1}{k}\). C'est un télescopage "à l'envers" (\(v_k - v_{k+1}\) au lieu de \(v_{k+1} - v_k\)), donc :

\[S_n = \sum_{k=1}^{n}\left(\frac{1}{k} - \frac{1}{k+1}\right) = \frac{1}{1} - \frac{1}{n+1} = 1 - \frac{1}{n+1} = \frac{n}{n+1}\]

Solution —

On reconnaît le pattern 4. On utilise l'identité \(k \cdot k! = (k+1)! - k!\) :

\[S_n = \sum_{k=1}^{n}\bigl((k+1)! - k!\bigr) = (n+1)! - 1!\ = (n+1)! - 1\]

Solution —

On réécrit le terme général :

\[\ln\!\left(1 + \frac{1}{k}\right) = \ln\!\left(\frac{k+1}{k}\right) = \ln(k+1) - \ln(k)\]

On reconnaît le pattern 2 avec \(v_k = \ln k\). Par télescopage :

\[S_n = \sum_{k=1}^{n}\bigl(\ln(k+1) - \ln k\bigr) = \ln(n+1) - \ln(1) = \ln(n+1)\]

Solution —

On reconnaît le pattern 3 : une factorielle au dénominateur. On cherche \(f\) tel que \(\dfrac{k}{(k+1)!} = f(k+1) - f(k)\).

Tâtonnement : on réécrit \(k = (k+1) - 1\) au numérateur :

\[\frac{k}{(k+1)!} = \frac{(k+1) - 1}{(k+1)!} = \frac{1}{k!} - \frac{1}{(k+1)!}\]

C'est un télescopage à l'envers avec \(v_k = \dfrac{1}{k!}\). Par télescopage :

\[S_n = \sum_{k=1}^{n}\left(\frac{1}{k!} - \frac{1}{(k+1)!}\right) = \frac{1}{1!} - \frac{1}{(n+1)!} = 1 - \frac{1}{(n+1)!}\]

Solution —

Étape 1 — Identifier le pattern : \(2k-1\) est un polynôme de degré 1 — c'est le pattern 0. On cherche \(v_k\) de degré 2 tel que \(v_k - v_{k-1} = 2k-1\).

Étape 2 — Trouver \(v_k\) par identification : on pose \(v_k = ak^2 + bk + c\) :

\[v_k - v_{k-1} = ak^2 + bk + c - \bigl(a(k-1)^2 + b(k-1) + c\bigr) = 2ak + (-a+b)\]

On identifie avec \(2k-1\) : \(2a = 2\) donc \(a=1\), et \(-a+b=-1\) donc \(b=0\). On obtient \(v_k = k^2\).

Vérification : \(k^2 - (k-1)^2 = (k-(k-1))(k+(k-1)) = 2k-1\) ✓

Étape 3 — Télescopage sans déployer : on écrit \(2k-1 = k^2 - (k-1)^2\) et on sépare par linéarité :

\[S_n = \sum_{k=1}^{n}k^2 - \sum_{k=1}^{n}(k-1)^2\]

Dans la deuxième somme, on pose \(j = k-1\) :

• Borne inf. : \(k=1 \Rightarrow j=0\)
• Borne sup. : \(k=n \Rightarrow j=n-1\)
• Terme général : \((k-1)^2 = j^2\)

\[S_n = \sum_{k=1}^{n}k^2 - \sum_{j=0}^{n-1}j^2\]

On fait apparaître les parties communes — les termes de \(j=1\) à \(j=n-1\) sont présents dans les deux sommes et s'annulent :

\[S_n = \left(\sum_{k=1}^{n-1}k^2 + n^2\right) - \left(0^2 + \sum_{j=1}^{n-1}j^2\right) = n^2 - 0 = n^2\]

Solution —

Le dénominateur \(\sqrt{k}+\sqrt{k+1}\) contient des racines carrées — elles sont gênantes et on voudrait les éliminer.

On connaît l'identité \((a-b)(a+b) = a^2 - b^2\). On reconnaît \(\sqrt{k}+\sqrt{k+1}\) comme le facteur \((a+b)\) avec \(a = \sqrt{k}\) et \(b = \sqrt{k+1}\). On multiplie donc numérateur et dénominateur par \((\sqrt{k+1}-\sqrt{k})\) :

\[\frac{1}{\sqrt{k}+\sqrt{k+1}} \times \frac{\sqrt{k+1}-\sqrt{k}}{\sqrt{k+1}-\sqrt{k}} = \frac{\sqrt{k+1}-\sqrt{k}}{(\sqrt{k+1})^2-(\sqrt{k})^2} = \frac{\sqrt{k+1}-\sqrt{k}}{1} = \sqrt{k+1}-\sqrt{k}\]

Les racines ont disparu ! On reconnaît le pattern 2 — différence explicite — avec \(v_k = \sqrt{k}\). Par télescopage :

\[S_n = \sum_{k=1}^{n}\bigl(\sqrt{k+1}-\sqrt{k}\bigr) = \sqrt{n+1} - \sqrt{1} = \sqrt{n+1} - 1\]

Solution —

Le terme \(k(k-1)(k-2)\) est un produit de 3 entiers consécutifs — degré 3. Par l'analogie primitive, on cherche \(v_k\) de degré 4. En s'inspirant de l'exercice 11, on essaie \(v_k = k(k-1)(k-2)(k-3)\).

On calcule \(v_{k+1} - v_k\) :

\[v_{k+1} - v_k = (k+1)k(k-1)(k-2) - k(k-1)(k-2)(k-3)\] \[= k(k-1)(k-2)\bigl[(k+1)-(k-3)\bigr] = 4\cdot k(k-1)(k-2)\]

Donc \(k(k-1)(k-2) = \dfrac{v_{k+1}-v_k}{4}\). Par télescopage :

\[S_n = \frac{1}{4}\sum_{k=1}^{n}(v_{k+1}-v_k) = \frac{v_{n+1}-v_1}{4} = \frac{(n+1)n(n-1)(n-2) - 0}{4}\] \[S_n = \frac{(n+1)n(n-1)(n-2)}{4}\]

Solution —

On cherche à écrire \(F_k\) comme une différence. La relation de récurrence \(F_{n+2} = F_{n+1} + F_n\) donne directement :

\[F_k = F_{k+2} - F_{k+1}\]

C'est le pattern 2 — différence explicite — avec \(v_k = F_{k+1}\). Par télescopage :

\[\sum_{k=0}^{n} F_k = \sum_{k=0}^{n}(F_{k+2}-F_{k+1}) = F_{n+2} - F_1 = F_{n+2} - 1\]

Solution —

Le terme \(k\cdot 2^k\) mélange un polynôme (degré 1) et une exponentielle — le pattern 0 seul ne suffit pas. On cherche \(v_k = (ak+b)\cdot 2^k\) et on identifie.

On calcule \(v_{k+1} - v_k\) :

\[v_{k+1} - v_k = (a(k+1)+b)\cdot 2^{k+1} - (ak+b)\cdot 2^k = 2^k\bigl[2a(k+1)+2b - ak - b\bigr] = 2^k\bigl[ak + (2a+b)\bigr]\]

On identifie avec \(k\cdot 2^k\) : \(a = 1\) et \(2a+b = 0\) donc \(b = -2\). Donc \(v_k = (k-2)\cdot 2^k\).

Vérification : \(v_{k+1} - v_k = (k-1)\cdot 2^{k+1} - (k-2)\cdot 2^k = 2^k(2k-2-k+2) = k\cdot 2^k\) ✓

Par télescopage :

\[S_n = \sum_{k=1}^{n}(v_{k+1}-v_k) = v_{n+1} - v_1 = (n-1)\cdot 2^{n+1} - (-1)\cdot 2 = (n-1)\cdot 2^{n+1} + 2\]

Solution —

1. Calcul des premiers termes :

Attention — la borne inférieure de la somme intérieure en \(k\) est \(j\), pas 1. Elle bouge avec \(j\) : quand \(j\) augmente, la fenêtre de \(k\) se rétrécit par le bas.

\(j\)	Somme intérieure \(\displaystyle\sum_{k=j}^{n}\frac{1}{k}\)
\(j=1\)	\(\dfrac{1}{1}+\dfrac{1}{2}+\cdots+\dfrac{1}{n}\) — toute la somme harmonique
\(j=2\)	\(\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{n}\) — on perd le premier terme
\(j=3\)	\(\dfrac{1}{3}+\dfrac{1}{4}+\cdots+\dfrac{1}{n}\) — on perd les deux premiers

Pour \(n=3\) :

• \(j=1\) : \((2\cdot1-1)\left(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}\right) = 1 \times \frac{11}{6} = \frac{11}{6}\)
• \(j=2\) : \((2\cdot2-1)\left(\frac{1}{2}+\frac{1}{3}\right) = 3 \times \frac{5}{6} = \frac{15}{6}\)
• \(j=3\) : \((2\cdot3-1)\cdot\frac{1}{3} = 5 \times \frac{1}{3} = \frac{10}{6}\)

\[S_3 = \frac{11+15+10}{6} = \frac{36}{6} = 6\]

De même : \(S_1 = 1\), \(S_2 = 3\), \(S_3 = 6\).

2. Conjecture : on reconnaît les nombres triangulaires \(1, 3, 6, \ldots\) — ce sont les valeurs de \(\dfrac{n(n+1)}{2}\). On conjecture :

\[S_n = \frac{n(n+1)}{2}\]

3. Démonstration par changement d'ordre : on visualise la somme double dans un tableau triangulaire :

	\(k=1\)	\(k=2\)	\(k=3\)
\(j=1\)	\(\frac{2\cdot1-1}{1}\)	\(\frac{2\cdot1-1}{2}\)	\(\frac{2\cdot1-1}{3}\)
\(j=2\)	—	\(\frac{2\cdot2-1}{2}\)	\(\frac{2\cdot2-1}{3}\)
\(j=3\)	—	—	\(\frac{2\cdot3-1}{3}\)

On somme colonne par colonne : pour la colonne \(k\) fixé, \(j\) varie de 1 à \(k\). Le terme général est \(\dfrac{2j-1}{k}\), donc la somme de la colonne \(k\) vaut :

\[\frac{1}{k}\sum_{j=1}^{k}(2j-1)\]

Or \(\displaystyle\sum_{j=1}^{k}(2j-1) = k^2\) — c'est la somme des \(k\) premiers entiers impairs, démontrée dans l'exercice 8. Donc la colonne \(k\) vaut \(\dfrac{k^2}{k} = k\).

En sommant toutes les colonnes :

\[S_n = \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \quad\blacksquare\]

Solution —

Stratégie : on ne calcule pas \(H_n\) exactement — on le minore par une quantité qui tend vers \(+\infty\). Pour cela on regroupe les termes en blocs de taille doublante :

\[H_{2^n} = 1 + \underbrace{\frac{1}{2}}_{1 \text{ terme}} + \underbrace{\frac{1}{3}+\frac{1}{4}}_{2 \text{ termes}} + \underbrace{\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}}_{4 \text{ termes}} + \cdots\]

Minoration de chaque bloc : le bloc \(k\) va de \(\dfrac{1}{2^{k-1}+1}\) à \(\dfrac{1}{2^k}\). Il contient \(2^k - 2^{k-1} = 2^{k-1}\) termes, et le plus petit est \(\dfrac{1}{2^k}\). Donc :

\[\sum_{j=2^{k-1}+1}^{2^k}\frac{1}{j} \geq 2^{k-1} \times \frac{1}{2^k} = \frac{1}{2}\]

Pourquoi \(2^{k-1}\) termes ? Le nombre de termes de \(2^{k-1}+1\) à \(2^k\) est \(2^k - (2^{k-1}+1) + 1 = 2^{k-1}\) — on retrouve la formule du nombre de termes (section 0.2).

Conclusion : en sommant les \(n\) blocs :

\[H_{2^n} = 1 + \sum_{k=1}^{n}\underbrace{\sum_{j=2^{k-1}+1}^{2^k}\frac{1}{j}}_{\geq \frac{1}{2}} \geq 1 + \sum_{k=1}^{n}\frac{1}{2} = 1 + \frac{n}{2}\]

Comme \(1 + \dfrac{n}{2} \to +\infty\) et que \(H_n\) est croissante, on conclut \(H_n \to +\infty\).

Solution —

Le terme général \(\dfrac{i}{j}\) se factorise en \(u_i \cdot v_j\) avec \(u_i = i\) et \(v_j = \dfrac{1}{j}\). On applique la proposition sur le produit de deux sommes :

\[S = \sum_{i=1}^{n}\sum_{j=1}^{n} \frac{i}{j} = \left(\sum_{i=1}^{n} i\right)\!\left(\sum_{j=1}^{n} \frac{1}{j}\right) = \frac{n(n+1)}{2} \cdot H_n\]

où \(H_n = \displaystyle\sum_{j=1}^{n}\dfrac{1}{j}\) est le \(n\)-ième nombre harmonique.

Solution —

1. Ligne par ligne : pour \(i\) fixé, \(j\) va de \(1\) à \(i\) et le terme général \(\dfrac{1}{i}\) ne dépend pas de \(j\) :

\[\sum_{j=1}^{i} \frac{1}{i} = i \cdot \frac{1}{i} = 1\]

Donc :

\[S = \sum_{i=1}^{n} 1 = n\]

2. Changement d'ordre : par la formule triangulaire, pour \(j\) fixé, \(i\) va de \(j\) à \(n\) :

\[S = \sum_{j=1}^{n}\sum_{i=j}^{n} \frac{1}{i} = \sum_{j=1}^{n}\left(\frac{1}{j} + \frac{1}{j+1} + \cdots + \frac{1}{n}\right) = \sum_{j=1}^{n}(H_n - H_{j-1})\]

où l'on a utilisé \(\displaystyle\sum_{i=j}^{n}\dfrac{1}{i} = H_n - H_{j-1}\) (avec la convention \(H_0 = 0\)).

Donc :

\[S = \sum_{j=1}^{n}(H_n - H_{j-1}) = nH_n - \sum_{j=1}^{n} H_{j-1} = nH_n - \sum_{j=0}^{n-1} H_j\]

3. Identité : les deux expressions de \(S\) sont égales :

\[nH_n - \sum_{j=0}^{n-1} H_j = n\]

Soit :

\[\sum_{j=0}^{n-1} H_j = nH_n - n = n(H_n - 1)\]

Ou encore, en réindexant avec \(k = j+1\) :

\[\sum_{k=1}^{n} H_k = (n+1)H_n - n\]

Solution —

Ligne par ligne :

• \(i=1\) : 1 terme → 1
• \(i=2\) : 2 termes → 2
• \(i=3\) : 3 termes → 3
• \(i=4\) : 4 termes → 4
• Total : \(1+2+3+4 = 10\)

Colonne par colonne (après changement d'ordre, \(i\) va de \(j\) à \(4\)) :

• \(j=1\) : \(i\) de 1 à 4 → 4 termes → 4
• \(j=2\) : \(i\) de 2 à 4 → 3 termes → 3
• \(j=3\) : \(i\) de 3 à 4 → 2 termes → 2
• \(j=4\) : \(i\) de 4 à 4 → 1 terme → 1
• Total : \(4+3+2+1 = 10\) ✓

On retrouve la somme de Gauss — ce n'est pas un hasard : \(\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{i} 1 = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}\).

Solution —

Ligne par ligne :

• \(i=1\) : \(j\) de 1 à 1 → \((1+1) = 2\)
• \(i=2\) : \(j\) de 1 à 2 → \((2+1)+(2+2) = 3+4 = 7\)
• \(i=3\) : \(j\) de 1 à 3 → \((3+1)+(3+2)+(3+3) = 4+5+6 = 15\)
• Total : \(2+7+15 = 24\)

Colonne par colonne (après changement d'ordre, \(i\) va de \(j\) à \(3\)) :

• \(j=1\) : \(i\) de 1 à 3 → \((1+1)+(2+1)+(3+1) = 2+3+4 = 9\)
• \(j=2\) : \(i\) de 2 à 3 → \((2+2)+(3+2) = 4+5 = 9\)
• \(j=3\) : \(i\) de 3 à 3 → \((3+3) = 6\)
• Total : \(9+9+6 = 24\) ✓

Solution —

Ligne par ligne : pour \(i\) fixé, la somme intérieure \(\displaystyle\sum_{j=1}^{i} j\) est la somme de Gauss :

\[\sum_{j=1}^{i} j = \frac{i(i+1)}{2}\]

Donc :

\[S = \sum_{i=1}^{n} \frac{i(i+1)}{2} = \frac{1}{2}\sum_{i=1}^{n}(i^2 + i) = \frac{1}{2}\left(\sum_{i=1}^{n} i^2 + \sum_{i=1}^{n} i\right)\]

En utilisant les formules connues \(\displaystyle\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}\) et \(\displaystyle\sum_{i=1}^{n} i^2 = \dfrac{n(n+1)(2n+1)}{6}\) :

\[S = \frac{1}{2}\left(\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2}\right) = \frac{n(n+1)}{2}\left(\frac{2n+1}{6} + \frac{1}{2}\right) = \frac{n(n+1)}{2}\cdot\frac{2n+4}{6}\] \[S = \frac{n(n+1)(n+2)}{6}\]

Voie 2 — Par télescopage sur \(i(i+1)\) (sans utiliser les formules connues)

On veut téléscoper \(\displaystyle\sum_{i=1}^{n} i(i+1)\). On cherche \(v_i\) tel que \(v_{i+1} - v_i = i(i+1)\).

Essai naïf — On essaie \(v_i = i(i+1)\) (même degré que le terme) :

\[v_{i+1} - v_i = (i+1)(i+2) - i(i+1) = (i+1)\bigl[(i+2)-i\bigr] = 2(i+1)\]

Ce n'est pas \(i(i+1)\) — on obtient \(2(i+1)\), un degré en dessous. Cela confirme que la différence descend d'un degré : pour obtenir un produit de degré \(p\), il faut partir d'un produit de degré \(p+1\).

Essai 1 — On essaie \(v_i = i(i+1)(i+2)\) (degré 3, en partant de \(i\)) :

\[v_{i+1} - v_i = (i+1)(i+2)(i+3) - i(i+1)(i+2) = (i+1)(i+2)\bigl[(i+3)-i\bigr] = 3(i+1)(i+2)\]

Ce n'est pas \(i(i+1)\) — on obtient \((i+1)(i+2)\), décalé d'un cran. Le produit commence trop haut.

Observation : pour que \(i(i+1)\) apparaisse en facteur dans \(v_{i+1} - v_i\), il faut que les deux termes \(v_{i+1}\) et \(v_i\) aient \(i(i+1)\) en commun. Cela suggère de "décaler vers le bas" et d'essayer \(v_i = (i-1)i(i+1)\).

Essai 2 — On essaie \(v_i = (i-1)i(i+1)\) :

\[v_{i+1} - v_i = i(i+1)(i+2) - (i-1)i(i+1) = i(i+1)\bigl[(i+2)-(i-1)\bigr] = 3\cdot i(i+1) \quad ✓\]

Donc \(i(i+1) = \dfrac{v_{i+1}-v_i}{3}\). Par télescopage :

\[\sum_{i=1}^{n} i(i+1) = \frac{1}{3}\sum_{i=1}^{n}(v_{i+1}-v_i) = \frac{v_{n+1}-v_1}{3} = \frac{n(n+1)(n+2) - 0}{3} = \frac{n(n+1)(n+2)}{3}\]

D'où :

\[S = \frac{1}{2}\sum_{i=1}^{n} i(i+1) = \frac{n(n+1)(n+2)}{6} \quad\checkmark\]