Exercice 52

1. La partie $\big\{\frac{u_{k}}{k}\big\}$ est non vide et minorée par $0$ : elle a une borne inférieure $\lambda \geqslant 0$ (théorème 1). Par récurrence sur $q$, $u_{(q+1)k} \leqslant u_{qk} + u_{k} \leqslant (q + 1)\,u_{k}$. $\boxed{u_{qk} \leqslant q\,u_{k}}$

2. Si $r \geqslant 1$, $u_{n} \leqslant u_{qk} + u_{r} \leqslant q\,u_{k} + M_{k}$ ; si $r = 0$, $u_{n} \leqslant q\,u_{k}$. Comme $qk \leqslant n$ et $u_{k} \geqslant 0$, $\frac{q\,u_{k}}{n} = \frac{qk}{n}\cdot\frac{u_{k}}{k} \leqslant \frac{u_{k}}{k}$. $$\boxed{\frac{u_{n}}{n} \leqslant \frac{u_{k}}{k} + \frac{M_{k}}{n}}$$ 3. Soit $\varepsilon > 0$. Par la proposition 2, il existe $k$ tel que $\frac{u_{k}}{k} \leqslant \lambda + \varepsilon$. Pour $n \geqslant \max\big(k, \frac{M_{k}}{\varepsilon}\big)$, on obtient $\lambda \leqslant \frac{u_{n}}{n} \leqslant \lambda + 2\varepsilon$. $\boxed{\frac{u_{n}}{n} \xrightarrow[n \to +\infty]{} \lambda}$

4. Un mot de longueur $n + m$ sans deux $a$ consécutifs se découpe en un préfixe de longueur $n$ et un suffixe de longueur $m$, qui n'en contiennent pas non plus ; ce découpage est injectif, donc $u_{n+m} \leqslant u_{n}u_{m}$, et $(\ln u_{n})$ est sous-additive et positive. Un mot valide de longueur $n + 2$ se termine par $b$, précédé d'un mot valide de longueur $n + 1$, ou par $ba$, précédé d'un mot valide de longueur $n$ : $u_{n+2} = u_{n+1} + u_{n}$, avec $u_{1} = 2$ et $u_{2} = 3$. Ainsi $u_{n} = F_{n+2}$, et la formule de Binet du cours donne $$\ln u_{n} = (n + 2)\ln\varphi - \ln\sqrt{5} + \ln\Big(1 - \Big(\frac{\psi}{\varphi}\Big)^{n+2}\Big),$$ dont le dernier terme tend vers $0$, par l'encadrement de l'exercice 21. $$\boxed{\frac{\ln u_{n}}{n} \xrightarrow[n \to +\infty]{} \ln\varphi \approx 0{,}481}$$ Le lemme de Fekete donne l'existence de la limite sans calcul ; c'est ainsi que l'on définit l'entropie d'un système de mots, même lorsqu'aucune formule explicite n'est disponible.