<s>[INST] 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!

 [/INST] 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}
</s>