I am reading M. Ram Murty's paper on Ramanujan Graphs: http://www.mast.queensu.ca/~murty/ramanujan.pdf and I am having trouble in a particular section, which is Section 6 on page 17 titled Counting walks in reguar graphs (it's a rather short section of about half page). In particular, I do not understand the conclusion that $$A_1A_r=A_{r+1}+(k-1)A_{r-1}$$ and what follows.
To give some context, we are considering a $k-$regular graph $X$ and its associated adjacency matrix $A$. We wish to construct a family of matrices (of same size as $A$, the number of vertices)$\{A_r\}$ such that the $(x,y)$-th coordinate of $A_i$ is the number of proper walks of length $i$ between the vertices $x$ and $y$. Here, proper walk means a walk that does not backtrack, its is however permitted at all times though that, for a walk, proper or otherwise, to have repeated vertices, at least this is the way Murty defined it earlier.
Here is what I have. the quantity $A_1A_r$ enumerates the number of walks of length $r+1$ which are proper up to length $r$ but may become improper at the last step, i.e. it can backtrack at the last step. Now on the right hand side we have $A_{r+1}$ which enumerates the number of proper walks of length $r+1$, plus $(k-1)$ times the matrix that enumerates proper walks of length $r-1$, here understand we must add more to $A_{r+1}$ since this only has strictly proper walks, but I am having trouble understanding why it is the quantity $(k-1)A_{r-1}$ that we need.
Another thing, the equation $A^2=A_2+kI$ makes sense, as we need to add the improper walks of length 2 which come out from a vertex one step then backtrack immediately after, and for each vertex we have exactly $k$ of these. Now, if we use the fact that $A_0=I$ and $A_1=A$, then $A_1A_1=A^2$. Now use the equation which I don't understand yet $A_1A_r=A_{r+1}+(k-1)A_{r-1}$ and take $r=1$, we have $$A_1A_1=A_2+(k-1)I$$ We have just shown $A_1A_1=A^2$ thus $A^2=A_2+(k-1)I$, but this is a contradiction to $A^2=A_2+kI$. What am I missing here? Any help is appreciated!!
In addition, I also do not understand Proposition 11 at the end either, and help on that would be appreciated as well.
Given that $A_1 A_r$ gives walks of length $r+1$ that may be improper only in the last step, the difference $A_1 A_r - A_{r+1}$ should count walks that are improper in the last step. These walks consist of a proper walk for $r-1$ steps, followed by taking any non-backtracking edge from the last vertex and immediately retracing it. There are $k-1$ choices for this edge, so there are $(k-1) A_{r-1}$ such walks.
I think this equation can only be valid for $r>1$, however, explaining why you run into trouble with your $r=1$ example. The problem is that if $r-1=0$, then "a proper walk for $r-1$ steps, followed by taking any non-backtracking edge from the last vertex and immediately retracing it" has $k$ choices for the non-backtracking edge: a proper walk for $0$ steps doesn't have anywhere to backtrack, so any of the $k$ edges from the endpoint is a valid edge to take and then double back on.
The proposition at the end of that page is essentially a standard way of using a recurrence relation to obtain a generating function. Define $F(t) = \sum_{r \ge 0} A_r t^r$. Then we can use the identity $A_1A_r=A_{r+1}+(k-1)A_{r-1}$ to write down an equation that $F(t)$ must satisfy:
\begin{align} F(t) &= A_0 + A_1t + A_2t^2 + \sum_{r \ge 3} A_r t^r \\ &= A_0 + A_1t + A_2t^2 + \sum_{r \ge 3} (A_1 A_{r-1} - (k-1) A_{r-2}) t^r \\ &= A_0 + A_1t + A_2t^2 + A_1 t \sum_{r \ge 3} A_{r-1} t^{r-1} - (k-1)t^2 \sum_{r \ge 3} A_{r-2} t^{r-2} \\ &= A_0 + A_1t + A_2t^2 + A_1 t \left(F(t) - A_0 - A_1 t\right) - (k-1)t^2 (F(t) - A_0) \end{align} and by solving for $F(t)$ and substituting in the initial conditions for $A_0$, $A_1$, $A_2$, we should get the equation in Proposition 11.