Finding a recurrence for number of paths in a certain tree

Question

I have a graph which looks like this:

The question is to find a recurrence for $a_n$ - the number of paths of length $n$ that start in vertex $A$. How do you tackle these kind of problems? There is obviously something I need to notice, but what is it?

Answer 1

The graph is bipartite, and the set that contains $A$ contains only three vertices, so we can write a recurrence for them. Denoting the number of paths of length $n$ that start at the mirror image of $A$ by $b_n$ and those that start at the lower centre vertex by $c_n$, we have

$$ \pmatrix{a\\b\\c}_{n+2}=\pmatrix{3&1&1\\1&3&1\\1&1&1}\pmatrix{a\\b\\c}_n\;. $$