How to find the number of x-length walks between two vertices of a triangle

Question

This question is from my homework and I don't have any idea how to solve it. Find the number of 2019-length walks between two vertices of a triangle.

Answer 1

From each vertex of the triangle, you always have two choices, go left or go right (clockwise/anticlockwise).
Now say that you go $x$ times left and $y$ times right. Then $x + y = 2019$. Furthermore, you should take a look at $x-y$ (mod $3$) to arrive at the right vertex.

So the problem boils down to:

For every $0 < x < 2019$, check if $x - (2019 -x)$ (mod $3$) is as desired. Can you count how many such $x$ you can find?

Once you have all your $x$, you need to decide how to divide them, so do you go first all $x$ then all $y$, or do you split them up somehow.

Answer 2

Pick one vertex as the starting vertex. Let $A(n)$ be the number of walks of length $n$ that end at that vertex. Let $B(n)$ be the number of walks of length $n$ that end at a specific other vertex. Write a set of coupled recurrence relations involving them and solve them. Note that the number of walks ending at the third vertex is also $B(n)$. As you have two choices at each point, you must have $A(n)+2B(n)=2^n$