Devoir type n°2 (2 h) - Exercice 3

Pour tout entier $$n\ge 1$$ , posons la propriété $$P_{n}$$ : « pour tous sommets $$i$$ et $$j$$ , $$m_{ij}^{\left(n\right)}$$ est le nombre de chemins de longueur $$n$$ allant de $$i$$ à $$j$$ ».
$$\red{\text{Étape d'initialisation :}}$$
Un chemin de longueur $$1$$ allant de $$i$$ à $$j$$ est un arc allant de $$i$$ à $$j$$ : il y en a $$m_{ij}=m_{ij}^{\left(1\right)}$$ . La propriété $$P_{1}$$ est vraie.
$$\red{\text{Étape d'hérédité :}}$$
On suppose qu'il existe un entier $$k\ge 1$$ tel que la propriété $$P_{k}$$ soit vraie. Un chemin de longueur $$k+1$$ allant de $$i$$ à $$j$$ est formé d'un chemin de longueur $$k$$ allant de $$i$$ à un sommet $$l$$ , puis d'un arc allant de $$l$$ à $$j$$ : il y en a $$m_{il}^{\left(k\right)}\times m_{lj}$$ dont l'avant-dernier sommet est $$l$$ . Le nombre total est donc :
$$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 le coefficient de la ligne $$i$$ et de la colonne $$j$$ de $$M^{k}\times M=M^{k+1}$$ , c'est-à-dire $$m_{ij}^{\left(k+1\right)}$$ . Ainsi la propriété $$P_{k+1}$$ est vraie.
$$\red{\text{Conclusion :}}$$
Puisque la propriété $$P_{1}$$ est vraie et que nous avons prouvé l'hérédité, on peut en déduire, par le principe de récurrence, que pour tout entier $$n\ge 1$$ , on a $$P_{n}$$ vraie.

D'après la question $$1$$ , le coefficient de la ligne $$i$$ et de la colonne $$j$$ de $$M^{2}$$ est le nombre de chemins de longueur $$2$$ allant de $$i$$ à $$j$$ . En additionnant sur tous les sommets $$j$$ :

C'est la somme des coefficients de la troisième ligne de $$M^{3}$$ : $$1+0+2+0+1=4$$ .
Ainsi :