Let $G$ be a graph with adjacency matrix $A$ and let $m\geq 0$. That means, in $A$ the entries say how many edges there are between each two vertices. For example $A_{ij}=1$ means that there is 1 edge between vertex $i$ and vertex $j$.
Show: The number of paths of length $m$ from $i$ to $j$ is $(A^m)_{ij}$, the (ij)-th entry of $A^m$.
For $m=0$ this seems clear, because the only paths of length 0 are the empty paths at each vertex. That means: I can only get from a vertex $i$ to a vertex $j$ in 0 steps if $i=j$.
For $m=1$ this is clear, too, because then I have $A^1=A$ itself… and the entries are exactly the paths of length 1 from i to j.
But how to prove that for $m\geq 2$?
Edit:
Maybe by induction?
For m=1 it is obviously correct.
Now suppose the statement is correct for $m$.
Show it is correct for $m+1$.
If we want to count the paths of length m+1 to get from i to j, then we have to count the possibilities to get from i to a vertice k in m steps and then in 1 step from k to j.
By induction, this number is
$$
\sum_{k\in V(G)}(A^m)_{ik}\cdot (A)_{kj}, (*)
$$
where $V(G)$ is the set of vertices of the graph $G$.
But $(*)$ is nothing else but $(A^{m+1}){ij}$.
Best Answer
Hint: use induction. In the induction step, consider how to make all paths of length $n$ to a vertex from paths of length $n-1$ to other vertices.