PROBLÈME D'ALGÈBRE : SOMMES ET COEFFICIENTS BINOMIAUX

Un panorama progressif des techniques de sommation en classe de MPSI.

Partie I : Les Fondations et la Formule du Binôme

Soit n un entier naturel. On rappelle la formule du binôme de Newton permettant de développer (1 + x)ⁿ pour tout réel x.

En évaluant judicieusement la fonction f : x ↦ (1 + x)ⁿ, déterminer la valeur de la somme des coefficients binomiaux :
\[S_0 = \sum_{k=0}^{n} \binom{n}{k}\]
De même, pour n ≥ 1, calculer la somme alternée suivante et donner son interprétation en termes de cardinaux de sous-ensembles :
\[A_0 = \sum_{k=0}^{n} (-1)^k \binom{n}{k}\]
En déduire les valeurs respectives de la somme des coefficients pairs \(\sum_{p=0}^{\lfloor n/2 \rfloor} \binom{n}{2p}\) et de la somme des coefficients impairs \(\sum_{p=0}^{\lfloor (n-1)/2 \rfloor} \binom{n}{2p+1}\).

L'objectif de cette partie est l'étude de la présence d'un facteur polynomial devant le coefficient binomial. Soit n ≥ 1.

L'identité d'absorption (ou du pion) : Montrer algébriquement que pour tout entier k tel que 1 ≤ k ≤ n, on a :
\[k \binom{n}{k} = n \binom{n-1}{k-1}\]
En déduire, par un changement d'indice rigoureux, la valeur de la somme :
\[S_1 = \sum_{k=0}^{n} k \binom{n}{k}\]

Retrouver ce résultat en dérivant la fonction f introduite à la Partie I.
En écrivant le polynôme k² sous la forme k(k - 1) + k, établir que :
\[S_2 = \sum_{k=0}^{n} k^2 \binom{n}{k} = n(n+1)2^{n-2}\]

On s'intéresse ici aux sommes où l'indice supérieur du coefficient binomial varie. Soit p un entier naturel fixé.

Rappeler la formule de Pascal reliant \(\binom{k}{p}\), \(\binom{k}{p+1}\) et \(\binom{k+1}{p+1}\).
À l'aide d'un télescopage, démontrer la formule dite de la crosse de hockey pour tout entier n ≥ p :
\[S_3 = \sum_{k=p}^{n} \binom{k}{p} = \binom{n+1}{p+1}\]

Soient n, m et r trois entiers naturels.

En développant de deux manières différentes l'expression polynomiale (1 + X)ⁿ(1 + X)^m = (1 + X)^n+m, démontrer l'identité de Vandermonde :
\[\sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k} = \binom{n+m}{r}\]
En utilisant la propriété de symétrie des coefficients binomiaux, en déduire la valeur remarquable de la somme des carrés :
\[S_4 = \sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}\]

On cherche à calculer la somme \(\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \dots\) en sommant de 3 en 3. On note j = e^2iπ/3.

Déterminer la valeur de la somme 1 + j^k + j^2k selon les valeurs de l'entier k modulo 3.
En développant (1 + 1)ⁿ + (1 + j)ⁿ + (1 + j²)ⁿ à l'aide du binôme de Newton, exprimer la somme suivante sous forme réelle :
\[S_5 = \sum_{k=0}^{\lfloor n/3 \rfloor} \binom{n}{3k}\]

En évaluant \(f(x)=(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k\) en \(x = 1\) :
\[S_0 = (1+1)^n = \mathbf{2^n}\]
En évaluant \(f(x)\) en \(x = -1\) pour \(n \ge 1\) :
\[A_0 = (1-1)^n = \mathbf{0}\]
Interprétation : Il y a autant de sous-ensembles de cardinal pair que de sous-ensembles de cardinal impair.
Par combinaisons linéaires \(\frac{S_0 + A_0}{2}\) et \(\frac{S_0 - A_0}{2}\) :
\[\sum_{p=0}^{\lfloor n/2 \rfloor} \binom{n}{2p} = \mathbf{2^{n-1}} \quad \text{et} \quad \sum_{p=0}^{\lfloor (n-1)/2 \rfloor} \binom{n}{2p+1} = \mathbf{2^{n-1}}\]

Par définition factorielle pour \(1 \le k \le n\) :
\[k \binom{n}{k} = k \frac{n!}{k!(n-k)!} = \frac{n \cdot (n-1)!}{(k-1)!(n-1-(k-1))!} = \mathbf{n \binom{n-1}{k-1}}\]
Le terme pour \(k=0\) étant nul, l'identité du pion et le changement d'indice \(j=k-1\) donnent :
\[S_1 = \sum_{k=1}^{n} n \binom{n-1}{k-1} = n \sum_{j=0}^{n-1} \binom{n-1}{j} = \mathbf{n 2^{n-1}}\]

Alternative : Obtenu directement en évaluant la dérivée \(f'(x) = n(1+x)^{n-1}\) en \(x=1\).
En écrivant \(k^2 = k(k-1) + k\) et en appliquant deux fois l'identité du pion :
\[S_2 = \sum_{k=2}^{n} n(n-1)\binom{n-2}{k-2} + S_1 = n(n-1)2^{n-2} + n2^{n-1} = \mathbf{n(n+1)2^{n-2}}\]

Formule de Pascal écrite sous forme de différence :
\[\binom{k}{p} = \binom{k+1}{p+1} - \binom{k}{p+1}\]
Par télescopage de la relation précédente pour \(k\) allant de \(p\) à \(n\) :
\[S_3 = \sum_{k=p}^{n} \left[\binom{k+1}{p+1} - \binom{k}{p+1}\right] = \binom{n+1}{p+1} - \binom{p}{p+1} = \mathbf{\binom{n+1}{p+1}} \quad \text{car } \binom{p}{p+1}=0\]

Par identification du coefficient de \(X^r\) dans l'égalité \((1+X)^n(1+X)^m = (1+X)^{n+m}\) développé via le produit de Cauchy :
\[\sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k} = \mathbf{\binom{n+m}{r}}\]
En posant \(m=n\) et \(r=n\), et en utilisant la symétrie \(\binom{n}{n-k}=\binom{n}{k}\) :
\[S_4 = \sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k} = \mathbf{\binom{2n}{n}}\]

Comme \(1+j+j^2=0\) et \(j^3=1\), la somme \(1+j^k+j^{2k}\) vaut \(\mathbf{3}\) si \(k \equiv 0 \pmod 3\), et \(\mathbf{0}\) sinon.
En sommant les trois développements binomiaux de \((1+1)^n\), \((1+j)^n\) et \((1+j^2)^n\) :
\[2^n + (1+j)^n + (1+j^2)^n = \sum_{k=0}^{n} \binom{n}{k} (1+j^k+j^{2k}) = 3 \sum_{p=0}^{\lfloor n/3 \rfloor} \binom{n}{3p} = 3 S_5\]
Avec \(1+j = e^{i\pi/3}\) et \(1+j^2 = e^{-i\pi/3}\), la formule trigonométrique donne :
\[S_5 = \mathbf{\frac{1}{3} \left( 2^n + 2\cos\left(\frac{n\pi}{3}\right) \right)}\]