Pavage par des dominos

Soit {{\mathcal U}_{n}} un rectangule de 4*n cases.
Soit {u_{n}} le nombre de façons de remplir {{\mathcal U}_{n}} par des dominos (horizontaux ou verticaux).
On voit ici un exemple de remplissage de {{\mathcal U}_{9}} :
article-28-01-17-fig1

  1. Trouver une relation de récurrence sur les {u_{n}}.
    Indication : comment la dernière colonne a-t-elle été remplie?
  2. Écrire une fonction Python calculant {u_n}.
    Vérifier que {u_{30}=21096536145301}.
  3. On définit {P(x)=x^4-x^3-5x^2-x+1}.
    Déterminer ses racines {x_{1}\lt x_{2}\lt x_{3}\lt x_{4}}.
    Vérifier numériquement avec Python.
  4. Prouver que, pour tout {n\in\mathbb{N}}: {u_{n}=\dfrac1{\sqrt{29}}(-x_{1}^{n+1}\!-\!x_{2}^{n+1}\!+\!x_{3}^{n+1}\!+\!x_{4}^{n+1})}
  5. Montrer que, sur un intervalle à préciser : {\displaystyle\sum_{n=0}^{+\infty}u_{n}x^n=\dfrac{1-x^2}{P(x)}}

Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez :