Recurrence relations - walk on a graph

Question

given the following undirected graph:

I need to find a recurrence relation that describes the number of possible walks starting at point A.

Well, naive me Iv'e defined $ a_n $ and tried to find the rule, but I got to a dead end. Eventually, I looked up the answer and found that they have defined two relations:

$ a_n $ - for walks start from A or D
$ b_n $ - for walks start from B or C

Then, it is easy to see that: $$ a_n = 2b_{n-1} \quad\quad b_n = 2a_{n-1} + b_{n-1} $$

And this one is pretty easy to solve..

BUT it did not come to my mind before looking at the answers!

In a matter of fact, I never really understood in what cases I should define more than one relation, and why in this specific case it is the right way to do that?

As you understand, I don't need the answers for the specific problem, but want to learn the way of thinking about this kind of questoins, since I keep doing mistakes in them.

Thanks!

Answer 1

The interesting bits are the initial condition and the recursion step from a $n$ problem instance to a $n+1$ problem instance.

If $a_n$ is the number of paths of length $n$, starting at $A$ or $D$, then $a_0 = 2$, thus $(A)$ and $(D)$, or $a_1 = 2 + 2 = 4$, thus $(A,B)$, $(A,C)$, $(D,B)$, $(D,C)$.

Now looking at $a_{n+1}$: We can split a path of length $n+1$ into one of length $1$ and one of length $n$. If we start at $A$, the $1$ hop leads to $B$, where have $b_n/2$ paths or to $C$, where we have $b_n/2$ paths as well. So we got $b_n$ paths starting from $A$. Considering the paths starting from $D$ give the same, we end up with $a_{n+1} = (b_n/2 + b_n/2) + (b_n/2 + b_n/2) = 2 b_n$ or $a_n = 2 b_{n-1}$.

Now looking at $b_{n+1}$: We have three one hops starting at $B$. To $A$, where we have $a_n/2$ paths of length $n$ starting, to $D$ where again $a_n/2$ paths of length $n$ originate, finally to $C$, where we got $b_n/2$ paths starting. This gives $b_{n+1}/2 = a_n/2 + a_n/2 + b_n/2$ or $b_{n+1} = 2 a_n + b_n$ or $b_n = 2 a_{n-1} + b_{n-1}$.

Answer 2

There is a general tool to reason about various numbers of walks in an (undirected) graph - the adjacency matrix. If we have a graph $G$ with adjacency matrix $A$, then the row of a vertex $v$ in $A$ tells us the number of length-1 walks to each other vertex. Similarly, the row of $v$ in $A^2$ tells us the number of length-2 walks, and so on, the row of $v$ in $A^n$ tells us the numbers of length $n$-walks to any other vertex. The recurrence you're looking for will pop up from the equality $A^{n+1}=A\times A^n$.

You can compute fancier things than that, if you multiply $A^n$ on the left with an appropriate vector, such as find the number of walks that start in a given set of the vertices and end in a given set of the vertices and so on. The idea also generalizes to directer graphs and multigraphs.

EDIT: oops that's not what the question was about. OK, so general intuition for recurrences is not that easily made explicit, it takes some time and experience. However, there are several things that help:

• usually you have some situation for $n$ and you want to find some quantity $q(n+1)$ describing the situation for $n+1$. Don't shy away from assuming any information about the $n$ case you might, and just try to write down an expression for $q(n+1)$ even if it involves things other than $q(n)$, such as some $r(n)$ or $s(n)$ or whatever. Then when you've identified which parts of the information about the $n$ case are useful, you can think about finding them recursively; often, they will be related to one another and to $q$. You need to get a feeling for when you need to assume you have more information (the $r,s$) at the $n$ case than the problem explicitly asks from you.
• Do dynamic programming questions, I think they help a lot with that kind of problems.