http://en.wikipedia.org/wiki/Mathematical_induction

I won't provide a proof, but here's how you can look at it. For a given n > 3, the answer f(n) is : f(n) = 3^(n-1) — f(n-1), f(2) = 3. The reason this is true is that you can move arbitrarily the first n-1 moves, each time choosing from 3 possibilities (hence the 3^(n-1)), and then go back to D on last n-th move. However, this isn't possible if after n-1 moves you end up in D, which is f(n-1), hence the subtraction.

So the answer f(n) is : 3^(n-1) — 3^(n-2) + 3^(n-3) — ... until 3^1.

I think the algorithm somehow uses this idea, I'm not sure how though.