Démontrer le nombre de chemins de longueur n avec la matrice d'adjacence - Exercice 1

Un chemin de longueur $$1$$ allant de $$i$$ à $$j$$ est formé d'un seul arc allant de $$i$$ à $$j$$ . Il y en a donc $$m_{ij}$$ , et $$m_{ij}=m_{ij}^{\left(1\right)}$$ car $$M^{1}=M$$ .
La propriété est vraie au rang $$1$$ .

Un chemin de longueur $$k+1$$ allant de $$i$$ à $$j$$ est formé d'un chemin de longueur $$k$$ allant de $$i$$ à un sommet $$l$$ , suivi d'un arc allant de $$l$$ à $$j$$ .
Pour un sommet $$l$$ fixé, il y a $$m_{il}^{\left(k\right)}$$ chemins de longueur $$k$$ allant de $$i$$ à $$l$$ (hypothèse de récurrence) et $$m_{lj}$$ arcs allant de $$l$$ à $$j$$ , donc $$m_{il}^{\left(k\right)}\times m_{lj}$$ chemins de longueur $$k+1$$ allant de $$i$$ à $$j$$ dont l'avant-dernier sommet est $$l$$ .
En additionnant pour $$l$$ allant de $$1$$ à $$p$$ , le nombre de chemins de longueur $$k+1$$ allant de $$i$$ à $$j$$ est :
$$m_{i1}^{\left(k\right)}\times m_{1j}+m_{i2}^{\left(k\right)}\times m_{2j}+\cdots +m_{ip}^{\left(k\right)}\times m_{pj}$$
C'est la somme des produits des coefficients de la ligne $$i$$ de $$M^{k}$$ par ceux de la colonne $$j$$ de $$M$$ , c'est-à-dire le coefficient de la ligne $$i$$ et de la colonne $$j$$ de $$M^{k}\times M=M^{k+1}$$ , soit $$m_{ij}^{\left(k+1\right)}$$ .
Ainsi la propriété est vraie au rang $$k+1$$ .

La propriété est vraie au rang $$1$$ et elle est héréditaire, donc, d'après le principe de récurrence, pour tout entier $$n\ge 1$$ :