Démontrer l'expression de la suite de Stern

Bonjour !

La suite de Stern $(s_n)_{n \in \mathbf N}$ est définie par :

La suite $(u_n)_{n \in \mathbf N}$ l'est par :

où $x \ \text{mod} \ 2$ désigne le reste de la division euclidienne de $x \in \mathbf R$ par $2$. $u_{n+1}$ est en fait le nombre d'entiers impairs sur la $n$^ème diagonale du triangle de Pascal :

L'objectif est de montrer que $(s_n) = (u_n)$, ce qui est vrai.

Pour ce faire, il suffit de montrer que $s_0 = u_0$, $s_1 = u_1$ et que $(u_n)$ vérifie la relation de récurrence de $(s_n)$. Autrement dit, il suffit de montrer :

Mais je bloque sur les deux derniers points. Auriez-vous des idées ?

Merci.

PS : j'ai des bugs de connexion et ne vois pas les balises Math. J'espère qu'il n'y a pas d'erreur.

Je ne sais pas pour les formules de combinatoire, mais en passant par le triangle de Pascal modulo 2 qui est comme le triangle de Sierpiński, on peut peut-être constater que la propriété est vérifiée (un peu comme avec Fibonacci, sauf que pour Fibonacci c'est plus facile de faire plus que constater). Ce n'est pas très joli mais bon.

Pour voir que $u_n = s_n$, peut-être peut-on passer par $u_{2^n + k} = u_k + u_{2^n - k}$ que l'on voit sur le triangle (avec $0 \leq k \leq 2^n$). On commence par montrer que $u_{2n} = u_n$ par récurrence forte (si $k$ est pair, le dernier bit à $0$ n'influe pas dans $u_k$ et $u_{2^n - k}$, donc dans $u_{2^n + k}$). Ensuite, pour montrer que $u_{n + n+1} = u_n + u_{n+1}$, on écrit $n$ de la forme $2^m + k$ avec $0 \leq k < 2^m$ (on extrait le premier bit à $1$). Cela revient donc à montrer que $u_{2^{m+1} + (2k+1)} = u_{2^m + k} + u_{2^m + (k+1)}$. On suppose la formule que l'on veut montrer par récurrence forte. On applique la formule de définition de $u$ aux deux termes, puis la formule que l'on veut montrer dans le terme de droite sur $u_k + u_{k+1}$ et sur $u_{2^m - k} + u_{2^m - (k+1)}$. Ensuite, je crois que l'on a une preuve (pas certain des détails), mais ça n'est pas très éclaircissant.

Je ne sais pas si ça te convient de passer par là.

edit : erreur dans latex (je ne vois pas le rendu lorsque je clique sur « aperçu »).

Merci pour ta réponse. Pourrais-tu développer cela :

Pour voir que $u_n = s_n$, peut-être peut-on passer par $u_{2^n + k} = u_k + u_{2^n - k}$ que l'on voit sur le triangle (avec $0 \leq k \leq 2^n$).

Je reprends pour la construction du triangle modulo 2.

Premièrement, on se place dans $\mathbb{Z}/p\mathbb{Z}$ avec $p$ premier et on fait la même construction que le triangle de Pascal. Ici, ce qui nous intéresse est $p=2$.

On compte les lignes du triangle en partant de $0$. Aucun $0$ ne peut apparaitre avant la ligne $p$ en utilisant la formule $\frac{(a+b)!}{a!b!}$ avec $0 \leq a+b < p$. À la ligne $p$, on va se retrouver avec quelque chose de la forme $1,0,\dots,0,1$ toujours en utilisant la même formule (avec $p+1$ nombres).

Ainsi, le triangle va se répéter deux fois jusqu'à la ligne $2p$. À cette ligne, on retrouvera la ligne $2$ avec des $0$ intercalés entre les nombres (chacun des deux triangles répliqués produira $1,0,\dots,0,1$, avec les deux $1$ du milieu qui se somment pour donner $2$). On va avoir un truc de la forme $1,0,\dots,0,2,0,\dots,0,1$. Les lignes suivantes sont encore le début du triangle répliqué (dont les coefficients sont multipliés par $1$ ou $2$), puis à la ligne $3p$ on se retrouve avec la ligne $3$ et des zéros intercalés. Ainsi de suite jusqu'à la ligne $p^2$ qui sera de la forme $1,0,\dots,0,1$. On réitère le raisonnement sur $2p^2$, jusqu'à $p^3$ et ainsi de suite.

On voit alors apparaitre une figure similaire au triangle de Sierpiński, avec des zones remplies de zéros (des triangles dont la pointe est en bas si on a dessiné le triangle de haut en bas). Les seuls zéros sont ceux qui sont dans ces zones.

On se place avec $p=2$. On nomme $u_n$ la somme comme tu l'as dit (et en fait on commence maintenant la numérotation des lignes à $1$). On considère la diagonale $2^n + k$ avec $0 \leq k \leq 2^n$. On coupe le triangle juste après la ligne $2^n$. La première partie de la diagonale est en-dessous de la ligne de découpe et est une copie de la diagonale $k$. La deuxième partie au-dessus ne se retrouve pas dans les termes précédents de $u$, mais on remarque que dans le cas particulier $p=2$, les triangles tronqués aux puissances de $2$ sont symétriques, et donc on retrouve en fait la diagonale $2^n - k$. Ainsi, on a $u_{2^n + k} = u_k + u_{2^n - k}$.