Paths of a Cycle

Question

I'm thinking through a problem, and I was having some trouble - I was wondering if I could get some help.

The problem is:

Let $u$ and $v$ be adjacent vertices in the cycle $C_5$. How many $(u,v)$-paths of length $20$ are there? (Undirected graph)

My thoughts so far - For the sake of example, let's reduce our cycle down to $C_3$ and try to look for some pattern. Let's set our path to length $5$. We have $1$ possible path here.

Let's now increase our cycle back to $C_5$ and set our length to $5$. There are $2$ possible paths here.

But I'm having trouble passing this empirical case into a more generalized case.

Any help?

Thank you!

Answer 1

The total distance travelled (clockwise, if $u$ is clockwise from $v$) can be $-16$, $-6$, $4$ or $14$. The corresponding numbers of clockwise and counterclockwise steps are $(2,18)$, $(7,13)$, $(12,8)$ and $(17,3)$, respectively, so the total number of paths is

$$ \binom{20}2+\binom{20}7+\binom{20}{12}+\binom{20}{17}=204820\;. $$