Number of walks of length k between 2 vertices in path graph Let $P_n$ define a path graph with $n$ vertices (example $P_5$ shown on image). Let $f_{n, k}(a, b)$ define a number of walks of length $k$ in $P_n$ starting from vertex $a$ and ending in vertex $b$.
Is there a formula for $f_{n, k}(a, b)$? Even after some research, I couldn't really find any resources about that problem (even though path graphs seem to be pretty simple objects so they should've already been studied very well). Thanks in advance!


We can use the adjacency matrix: $$f_{n,k}(a,b) = (A(P_n)^k)_{ab}$$ where $A(P_n)$ is the adjacency matrix of $P_n$. That adjacency matrix has the form $$\begin{bmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0 \\ 1 & 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & 1 & \cdots & 0 & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & 0 & 0 & \cdots & 1 & 0\end{bmatrix}$$ with $1$'s above and below the main diagonal, and zeroes everywhere else.
To get a closed form, we need to diagonalize $A(P_n)$. The eigenvalues are going to have the form $\lambda_j = 2 \cos \frac{j\pi}{n+1}$ for $j=1, \dots, n$, with the eigenvector $v^{(j)}$ of $\lambda_j$ proportional to $(\sin \frac{j\pi}{n+1}, \sin \frac{2j\pi}{n+1}, \dots, \sin \frac{n j \pi}{n+1})$. (This form of the eigenvector has norm $\sqrt{\frac{n+1}{2}}$; we could normalize it, but it's easier to just divide through by $\frac{n+1}{2}$ at the end.) Verifying these boils down to checking the trigonometric identity that $$\sin\left(\theta - \frac{j\pi}{n+1}\right) + \sin\left(\theta + \frac{j\pi}{n+1}\right) = 2 \cos \frac{j\pi}{n+1} \sin \theta$$ which tells us that the $i^{\text{th}}$ component of $A(P_n) v^{(j)}$ is $v^{(j)}_{i+1} + v^{(j)}_{i-1} = \lambda_j v^{(j)}_i$.
In the eigenvector basis, the standard basis vector $e^{(b)}$ is written as:
$$e^{(b)} = \frac{2}{n+1} \sum_{j=1}^n (v^{(j)} \cdot e^{(b)}) v^{(j)} = \frac{2}{n+1} \sum_{j=1}^n \sin \frac{bj\pi}{n+1} v^{(j)}$$
Multiplying through by $A(P_n)^k$, we get
$$
   A(P_n)^k e^{(b)} = \frac{2}{n+1} \sum_{j=1}^n \sin \frac{bj\pi}{n+1} \lambda_j^k v^{(j)} = \frac{2}{n+1} \sum_{j=1}^n \sin \frac{bj\pi}{n+1} \left(2 \cos\frac{j\pi}{n+1}\right)^k v^{(j)}.
$$
We want to take the $(a,b)$ entry of $A(P_n)^k$, which is equal to $e^{(a)} \cdot A(P_n)^k e^{(b)}$. So we get
\begin{align}
f_{n,k}(a,b) &= e^{(a)} \cdot A(P_n)^k e^{(b)} \\
   &= \frac{2}{n+1} \sum_{j=1}^n \sin \frac{bj\pi}{n+1} \left(2 \cos\frac{j\pi}{n+1}\right)^k (e^{(a)} \cdot v^{(j)}) \\
   &= \frac{2}{n+1} \sum_{j=1}^n \sin \frac{aj\pi}{n+1} \sin \frac{bj\pi}{n+1} \left(2 \cos\frac{j\pi}{n+1}\right)^k.
\end{align}
