Les chaînes du carré

Les chaînes du carré. On reprend le graphe du cours formé par le carré $A-B-C-D-A$ (sommets dans l'ordre $A,B,C,D$), de matrice d'adjacence $M$, dont on rappelle le carré :

$$M=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right)\text{et}{M}^2=\left(\begin{array}{cccc}2& 0& 2& 0\\ 0& 2& 0& 2\\ 2& 0& 2& 0\\ 0& 2& 0& 2\end{array}\right)$$

• Calculer $M^3$ et montrer que $M^3=4M$.
• Démontrer par récurrence que, pour tout entier $k\ge 0$, $M^{2k+1}=4^{k}M$, puis en déduire que $M^{2k}=4^{k-1}{M}^2$ pour tout $k\ge 1$.
• Combien y a-t-il de chaînes de longueur $7$ de $A$ à $B$ ? de $A$ à $A$ ? Combien de chaînes de longueur $6$ de $A$ à $C$ ?
• Expliquer sans calcul pourquoi aucune chaîne de longueur impaire ne relie un sommet à lui-même.
• Montrer que, pour tout $n\ge 1$, le nombre total de chaînes de longueur $n$ partant de $A$ est $2^n$, et retrouver ce résultat directement.