Solution pour le challenge n° 22

Notons, pour tout $n\in\mathbb{N}$ et pour tout ensemble $E$ de cardinal $n$ :

$A_{n}$ le nombre de parties de $E$ de cardinal congru à 0 modulo 3
$B_{n}$ le nombre de parties de $E$ de cardinal congru à 1 modulo 3
$C_{n}$ le nombre de parties de $E$ de cardinal congru à 2 modulo 3

Comme le nombre de parties de $E$ de cardinal $k$ est égal à $\binom{n}{k},$ alors :

$A_{n}=\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\cdots$

sachant que cette somme doit se poursuivre “tant que c’est possible”, ce qui veut dire qu’on ajoute les entiers $\displaystyle{\binom{n}{3k}}$ tant que $3k\leqslant n$ . Bref :

$\boxed{A_{n}=\sum_{k=0}^{\left\lfloor n/3\right\rfloor }\binom{n}{3k}}$

où le symbole $\left\lfloor x\right\rfloor$ désigne la partie entière par défaut du réel $x,$ c’est-à-dire le plus grand entier inférieur ou égal à $x$ . On voit de la même manière que :

$B_{n}=\sum_{k=0}^{\left\lfloor (n-1)/3\right\rfloor }\binom{n}{3k+1}\qquad\text{et}\qquad C_{n}=\sum_{k=0}^{\left\lfloor (n-2)/3\right\rfloor }\binom{n}{3k+2}$

Afin, de calculer explicitement $A_{n},$ voici un astuce géniale.

On va faire intervenir le nombre complexe :

$j=e^{\frac{2i\pi}{3}}=-\frac{1}{2}+i\frac{\sqrt{3}}{2}$

qui a le bon goût d’être une “racine cubique de l’unité” ce qui signifie simplement que $j^{3}=1.$

En effet, d’après la formule de Moivre :

$j^{3}=\left(e^{\frac{2i\pi}{3}}\right)^{3}=e^{2i\pi}=1$

En conséquence, la suite géométrique $\left(j^{n}\right)_{n\geqslant0}$ est périodique, de période $3,$ ce qui va s’avérer crucial pour la suite des opérations.

On observe en outre que :

$1+j+j^{2}=\frac{1-j^{3}}{1-j}=0\qquad\left(\spadesuit\right)$

Maintenant, appliquons la formule du binôme :

$\left(1+1\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}=A_{n}+B_{n}+C_{n}\qquad\left(1\right)$

On a simplement séparé les $n+1$ termes qui composent cette somme en trois groupes : d’un côté les termes d’indice multiple de 3, d’un autre côté ceux dont l’indice est congru à 1 modulo 3 et, pour finir, ceux dont l’indice est congru à 2 modulo 3.

Compte tenu de ce qui a été dit au sujet du nombre complexe $j,$ on dispose de deux égalités supplémentaires :

$\left(1+j\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}j^{k}=A^{n}+jB_{n}+j^{2}C_{n}\qquad\left(2\right)$

$\left(1+j^{2}\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}j^{2k}=A_{n}+j^{2}B_{n}+jC_{n}\qquad\left(3\right)$

Si l’on ajoute membre à membre les relations (1), (2) et (3), tout en tenant compte de $\left(\spadesuit\right),$ il vient :

$2^{n}+\left(1+j\right)^{n}+\left(1+j^{2}\right)^{n}=3A_{n}$

Or, $j$ et $j^{2}$ sont conjugués et, par conséquent, $\left(1+j\right)^{n}$ et $\left(1+j^{2}\right)^{n}$ sont aussi conjugués.

Ceci conduit à :

$\boxed{A_{n}=\frac{1}{3}\left[2^{n}+2\thinspace\text{Re}\left(\left(1+j\right)^{n}\right)\right]}$

Voilà déjà une formule explicite pour $A_{n},$ mais elle est un peu “compliquée”. On sait bien que $A_{n}$ est un entier naturel et l’on préférerait disposer d’une formule plus simple.

Pour cela, on va tâcher de faire disparaître toute référence aux nombres complexes et à la trigonométrie…

On observe que, pour tout $n\in\mathbb{N}$ :

$\left(1+j\right)^{n}=\left(-j^{2}\right)^{n}=e^{in\pi/3}$

d’où, en passant aux parties réelles :

$\text{Re}\left(\left(1+j\right)^{n}\right)=\cos\left(\frac{n\pi}{3}\right)=\left\{ \begin{array}{cc}1 & \text{si }n\equiv0\pmod{6}\\\\\frac{1}{2} & \text{si }n\equiv1\pmod{6}\\\\-\frac{1}{2} & \text{si }n\equiv2\pmod{6}\\\\-1 & \text{si }n\equiv3\pmod{6}\\\\-\frac{1}{2} & \text{si }n\equiv4\pmod{6}\\\\\frac{1}{2} & \text{si }n\equiv5\pmod{6}\end{array}\right.$

Finalement :

$A_{n}=\left\{ \begin{array}{cc}\frac{1}{3}\left(2^{n}+2\right) & \text{si }n\equiv0\pmod{6}\\\\\frac{1}{3}\left(2^{n}+1\right) & \text{si }n\equiv1,5\pmod{6}\\\\\frac{1}{3}\left(2^{n}-1\right) & \text{si }n\equiv2,4\pmod{6}\\\\\frac{1}{3}\left(2^{n}-2\right) & \text{si }n\equiv3\pmod{6}\end{array}\right.$

Passons à l’examen de la parité de $A_{n}.$ Cette question ne semble pas facile d’accès avec la formule explicite obtenue ci-dessus.

Pourtant, en rédigeant un programme de calcul de $A_{n}$ (voir en annexe pour une version écrite en Python) et en observant la parité de $A_{n}$ pour de petites valeurs de $n,$ on découvre une apparente régularité :

$1,\:1,\:1,\:2,\:5,\:11,\:22,\:43,\:85,\:170,\:341,\:683,\:1\thinspace366,\:2\thinspace731,\:5\thinspace461,\:10\thinspace922,\:...$

Pour $0\leqslant n\leqslant15,$ , les $A_{n}$ pairs sont $A_{3,}$ $A_{6},$ $A_{9},$ $A_{12}$ et $A_{15}.$

On conjecture donc naturellement que, pour tout $n\geqslant3$ :

$A_{n}\text{ est pair}\Leftrightarrow3\mid n$

ce qu’on va maintenant établir rigoureusement.

Pour cela, on va faire un petit raisonnement combinatoire.

Considérons un ensemble $E$ de cardinal $n+1$ et nommons $\alpha$ un élément particulier. Les parties de $E$ dont le cardinal est multiple de $3$ sont :

les parties de $E-\left\{ \alpha\right\}$ de cardinal multiple de $3,$
les unions du singleton $\left\{ \alpha\right\}$ avec une partie de $E-\left\{ \alpha\right\}$ de cardinal congru à 2 modulo 3

Par conséquent :

$A_{n+1}=A_{n}+C_{n}\qquad\left(\star\right)$

Considérons maintenant un ensemble de cardinal $n+2$ et nommons $\alpha,\beta$ deux éléments particuliers. Les parties de $E$ dont le cardinal est multiple de 3 sont :

les parties de $E-\left\{ \alpha,\beta\right\}$ de cardinal multiple de $3,$
les unions de l’un des deux singletons $\left\{ \alpha\right\}$ ou $\left\{ \beta\right\}$ avec une partie de $E-\left\{ \alpha,\beta\right\}$ de cardinal congru à 2 modulo 3
les unions de la paire $\left\{ \alpha,\beta\right\}$ avec une partie de $E-\left\{ \alpha,\beta\right\}$ de cardinal congru à 1 modulo 3

Par conséquent :

$A_{n+2}=A_{n}+2C_{n}+B_{n}\qquad\left(\star\star\right)$

Considérons enfin un ensemble de cardinal $n+3$ et nommons $\alpha,\beta,\gamma$ trois éléments particuliers. Les parties de $E$ dont le cardinal est multiple de 3 sont :

les parties de $E-\left\{ \alpha,\beta,\gamma\right\}$ de cardinal multiple de $3,$
les unions de l’un des trois singletons $\left\{ \alpha\right\} ,$ $\left\{ \beta\right\}$ ou $\left\{ \gamma\right\}$ avec une partie de $E-\left\{ \alpha,\beta,\gamma\right\}$ de cardinal congru à 2 modulo 3
les unions de l’une des trois paires $\left\{ \alpha,\beta\right\} ,$ $\left\{ \alpha,\gamma\right\}$ ou $\left\{ \beta,\gamma\right\}$ avec une partie de $E-\left\{ \alpha,\beta,\gamma\right\}$ de cardinal congru à 1 modulo 3
l’union de $\left\{ \alpha,\beta,\gamma\right\}$ avec une partie de $E-\left\{ \alpha,\beta,\gamma\right\}$ de cardinal multiple de 3

Par conséquent :

$A_{n+3}=2A_{n}+3C_{n}+3B_{n}\qquad\left(\star\star\star\right)$

En combinant $\left(\star\right),$ $\left(\star\star\right)$ et $\left(\star\star\star\right),$ on obtient la relation de récurrence linéaire d’ordre 3 suivante :

$\boxed{A_{n+3}=3A_{n+2}-3A_{n+1}+2A_{n}}$

Notons désormais : $q_{n}=A_{n}\mod2$ (c’est le reste de la division de $A_{n}$ par 2 : cet entier vaut 0 si $A_{n}$ est pair et 1 sinon). Alors, pour tout $n\in\mathbb{N}$ (en réduisant modulo 2 l’égalité précédente) :

$q_{n+3}=\left(q_{n+2}+q_{n+1}\right)\mod2$

Comme $\left(q_{0},q_{1},q_{2}\right)=\left(1,1,1\right),$ on voit que les premiers termes de la suite $\left(q_{n}\right)_{n\in\mathbb{N}}$ sont :

$1,\:1,\:1,\:0,\:1,\:1,\:0,\:1,\:1,\:0,\:1,\:1,\:0,\:1,\:1,\:0,...$

On peut aisément montrer par récurrence que, pour tout $k\in\mathbb{N}^{\star}$ :

$q_{3k}=0,\quad q_{3k+1}=q_{3k+2}=1$

ce qui permet de conclure.

Annexe : programmation en Python

Calcul des coefficients binomiaux (solution récursive, utilisant la formule du pion)

def binomial(n,k):
  if k == 0:
    return 1
  elif 2 * k > n:
    return binomial(n, n-k)
  else:
    return (n * binomial(n-1,k-1)) // k

Calcul de la somme $A_{n}=\sum_{k=0}^{\left\lfloor n/3\right\rfloor }\binom{n}{3k}$

def A(n):
  s = 0
  k = 0
  while k <= n:
    s += binomial(n, k)
    k += 3
  return s

Pour consulter l’énoncé, c’est ici

Partager cet article