Proof - raising adjacency matrix to $n$-th power gives $n$-length walks between two vertices

Solution 1:

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.