I came across the formula to find the number of walks of length $n$ between two vertices by raising the adjacency matrix of their graph to the $n$-th power.
I took me quite some time to understand why it actually works. I thought it would be useful to write the proof by induction for this in my own words.
Theorem: Raising an adjacency matrix $A$ of simple graph $G$ to the $n$-th power gives the number of $n$-length walks between two vertices $v_i$, $v_j$ of $G$ in the resulting matrix.
Proof by induction: Let $P(n)$ be the predicate that the theorem is true for $n$. We let $F^{(n)}_{ij}$ be the number of $n$-length walks between vertex $v_i$ and $v_j$. $P(n)$ is then the predicate that $F^{(n)}_{ij} = A^n_{ij}$. We proceed by induction on $n$.
Base case: $P(1)$
Case 1: $F^{(1)}_{ij} = A^{(1)}_{ij} = 1$ if $\{v_i, v_j\} \in E$, so there is is a walk of length $1$ between $v_i$, $v_j$.
Case 2: $F^{(1)}_{ij} = A^{(1)}_{ij} = 0$ if $\{v_i, v_j\} \notin E$, so there can't be any walk of length $1$ between $v_i$ and $v_j$.
In both cases $F^{(1)}_{i j} = A^{(1)}_{ij}$ holds, hence $P(1)$ is true.
Inductive step: $P(n+1)$ For purpose of induction, we assume $P(n)$ is true, that is $F^{(n)}_{i j} = A^{(n)}_{ij}$ holds for $n$.
We can express a walk of length $n+1$ from $v_i$ to $v_j$ as a $n$-length walk from $v_i$ to $v_k$ and a walk of length 1 from $v_k$ to $v_j$.
That means, the number of $n+1$-length walks from $v_i$ to $v_j$ is the sum over all walks from $v_i$ to $v_k$ times the number of ways to walk in one step from $v_k$ to $v_j$. Thus:
$$F^{(n+1)}_{ij} = \sum_{k=1}^{|V|} A_{kj}F^{(n)}_{ik} = \sum_{k=1}^{|V|} A_{kj}A^{(n)}_{ik}$$
Which is the formula for the dot-product, used in matrix multplications.
Any feedback appreciated.
Best Answer
Your idea looks correct. Just some remarks on your notation.
You chose $P(n)$ to denote the induction statement. And you (apparently) chose $P_{i,j}^{(n)}$ to denote the number of $v_i$-$v_j$-walks of length $n$. But you use it in the following inconsistent ways: $P(n)$, $P_{i,j}$, $P_{i,j}(n)$. The first one is the most irritating one because it conflicts with your notation for the induction statement. Please keep attention on being consistent with your notation. Mathematics is very exact and to be precise, when you defined $P_{i,j}^{(n)}$, the expression $P_{i,j}(n)$ has still no meaning and is undefined! It will probably be considered a typo, but better be sure and stick to standard or defined notations.
Please note that it is not wrong to use $P$ for both, but keep them distinct by indices or decoration. It however is recommended to use different letters for very different concepts $-$ there are 26 of them and many more symbols when using other alphabets.