Pour {n\geq1}, on note {U_n} un rectangle de quatre cases de hauteur et {n} cases de largeur. On note {u_n} le nombre de pavages par des dominos de deux cases adjacentes, horizontaux ou verticaux. Voici un exemple pour {U_9}.
Les surfaces {V_n} et {W_n} sont les rectangles incomplets ci-dessous, de hauteur quatre et de largeur totale {n}. La dernière colonne de {V_n} ne comporte que les deux cases du bas ; celle de {W_n} ne comporte que les deux cases centrales. On note {v_n} et {w_n} leurs nombres de pavages.
On a {u_1=v_1=w_1=1}. On convient de poser {u_0=1} et {v_0=w_0=0}. Les questions [P] utilisent Python.
1. (a) Pour {n\geq2}, exprimer {u_n,v_n,w_n} en fonction de termes de rang {n-1} ou {n-2}, en discutant le remplissage de la dernière colonne. Vérifier {u_2=5} et {u_3=11}.
1. (b) En déduire, pour {n\geq4}, {u_n=u_{n-1}+5u_{n-2}+u_{n-3}-u_{n-4}\tag{E}}Indication : exprimer {v_{n-1}-v_{n-3}} et {w_{n-1}-w_{n-3}} à l’aide de {u}.
1. (c) [P] Écrire
suite(n), renvoyant {[u_0,\ldots,u_n]} pour {n\geq3}. Vérifier {u_{30}=21096536145301}.2. (a) Déterminer exactement les racines de {P(X)=X^4-X^3-5X^2-X+1}. Indication : considérer {P(X)/X^2}.
2. (b) Placer les valeurs approchées de ces racines dans
x1,x2,x3,x4, dans l’ordre croissant.2. (c) [P] Retrouver ces valeurs avec un objet
poly1d et les ranger dans l’ordre croissant.3. (a) Montrer que, pour {n\in\mathbb N}, {u_n=\frac{-x_1^{n+1}-x_2^{n+1}+x_3^{n+1}+x_4^{n+1}}{\sqrt{29}}}
3. (b) [P] Utiliser cette expression pour retrouver {u_{30}}. Peut-on ainsi espérer obtenir les valeurs exactes pour de grands {n} ?
4. Montrer, sur un intervalle à déterminer, que {\frac{1-x^2}{1-x-5x^2-x^3+x^4}=\sum_{n=0}^{+\infty}u_nx^n}