Let $v$ and $w$ be distinct vertices in $K_n$. Let $p_m$ denote the number of paths of length $m$ from $v$ to $w$ in $K_n$, $1\leq m \leq n$.
$(a)$ $\hspace{1cm}$Derive a recurrence relation for $p_m$.
$(b)$ $\hspace{1cm}$Find an explicit formula for $p_m$.
HINT: Clearly $p_1=1$: there’s only one path of length $1$ from $v$ to $w$. A path of length $2$ from $v$ to $w$ must consist of an edge from $v$ to some vertex $u$ other than $w$ followed by the edge from $u$ to $w$, so there is one of these paths for each vertex $u$ that isn’t $v$ or $w$. There are $n-2$ such edges, so $p_2=n-2$. What about paths of length $3$ from $v$ to $w$? Such a path can be broken into a path of length $2$ from $v$ to some vertex $u\ne w$ followed by the edge from $u$ to $w$. Moreover, $u\ne v$, so there are $n-2$ possible choices for $u$. (I’m assuming here that your definition of path does not allow repeated vertices.) If there are $n-2$ choices for $u$, and $p_2$ paths of length $2$ from $v$ to each of these possible vertices $u$, what is $p_3$?
If you can answer that last question, you should be able to generalize the idea just a little to get the desired recurrence, and once you have the right recurrence, getting the closed form is pretty easy.