Choux(n)= l'exposant de la plus grande puissance de 2 qui divise n !

Choux(n) est donc le nombre de 0 qui finissent l'écriture en base 2 du nombre n !

Carottes(n) est le nombre de 1 dans la représentation binaire de n.

On vérifie que Choux(n) + Carottes(n)= n pour n dans {1 ;2} puis on le vérifie pour tout n par récurrence.

Supposons le résultat vrai pour n.

1) Supposons que n est pair. La représentation binaire de n finit alors par un 0 et on a Carottes(n + 1)=Carottes(n) + 1.

On a (n + 1) !=n ! x (n + 1) où n ! se termine par Choux(n) fois le chiffre 0 et n + 1 par un 1. Le produit se termine donc par Choux(n) fois le chiffre 0, ce qui s'écrit Choux(n + 1) = Choux(n).

On a donc Carottes(n +1) + Choux(n + 1)=Carottes(n) + 1 + Choux(n)=n + 1.

2) Supposons maintenant que n est impair. Sa représentation binaire se termine donc par k fois le chiffre 1 avec k>0. Le k + 1 -ème chiffre en partant de la droite est un 0.

n + 1 va alors se terminer par un chiffre 1 suivi de k chiffres 0. On a donc :

Carottes(n + 1)=Carottes(n) - k + 1  (car on a remplacé les k chiffres 0 par des 1 et un chiffre 0 par un 1).

D'autre part, le produit (n + 1) ! = n ! x (n + 1) est le produit d'un nombre qui se termine par Choux(n) chiffres 0 et d'un nombre qui finit par k chiffres 0. Ce produit finit donc par Choux(n)+ k chiffres 0. C'est-à-dire que Choux(n + 1) = Choux(n) + k.

On a donc Carottes(n + 1) + Choux(n + 1)=Carottes(n)-k + 1+ Choux(n) + k = Carottes(n) + Choux(n) + 1 = n + 1.