Hello, I'm trying to understand the following formula: F(n) = F(n-1) + 2F(n-2).
The original problem is:
Given three vertex A,B,C and a number of moves L, the edges are:
A to B
A to C
B to A
B to C
C to A
and C to B.
What the number of ways to go from A and get back to A, using L moves ?
I'm trying to figure out, why the above formula works for this problem, can you help me ? Thank you. Thank you.
there are two ways to start from A and get back to A in L moves:
1_start from A and then get back to A in L — 2 moves and then go to B or C and then back to A in this case, you need to count the number of ways to start from A and get back to A in L — 2 Moves, and then multiply the answer by 2, because you can move to B or C for the next move.
2_start from A and get to B or C in L — 2 moves, then get to A in 2 last moves(for example if you move to C in L-2 moves, then you'll have to go to B and then to A to complete the walk) in this case, you need to count the number of ways to start from A and get to B or C in L-2 moves which is equal to the number of ways to start from A and get back to A in L-1 moves.
so: f(l) = f(l-1) + 2f(l-2)
Suppose you have n moves, and think about where you should be in the n-1 move: it can't be A so it's either B or C. Let's say that you can get to B in n-1 moves with Fb(n-1) ways and you can get to C in n-1 moves with Fc(n-1) ways, obviously F(n) = Fb(n-1)+Fc(n-1) ( because you can't get from A back to A in only one move). So, one way to get to A in n+1 moves is to be at B in the (n-1)th move, go to C and then go to A and there are Fb(n-1) ways to do it, similarly if you are at C in the (n-1)th move, there are Fc(n-1) ways to go to A in n+1 moves. So if you are either in B or C in the n-1th move, you can go to A (in n+1 moves) with Fb(n-1)+Fc(n-1)=F(n) ways. However if you are in A in the n-1th moves, there are two ways: either go to B then go back to A or go to C and go back to A, but there are F(n-1) ways to be at A in the n-1th move ==> So overall F(n+1)=F(n)+2*F(n-1)
Very clear explanation, thank you.