Multiple probability and combinations style questions for a confused frog! Question: 
A frog has an equal probability of jumping left, right or staying stationary every minute. Consider the set of n-minute-long paths of the frog. Each such path
is given by an n-tuple over the set {L, R, S}, where L represents the
frog’s decision of jumping to the left, R stands for the right and S –
for staying in place.
(i) How many such paths contain no two identical consecutive steps?
For example, the path SLSRSLS is allowed, while SLLRSL is
not. [3 marks]
(ii) Assume that the frog catches a fly any time it jumps to the left
and two flies any time it jumps to the right, but it gets no more
flies when it stays in its place. In how many paths of length n the
total number of flies caught will be divisible by 3? [3 marks]
(iii) Give a recursive formula T(n) for the number of n-minute-long
paths on which the frog catches an even number of flies. Calculate T(5).
[3 marks]
(iv) In how many such paths the frog catches an even number of
flies in last two steps? [3 marks]
(v) Use your solution to part (c) to give a recursive formula F(n) for
the number of paths where the number of flies caught in last two
steps is even and the total number of flies caught along the path
is even? Calculate F(5). [3 marks]
Solution: 
for part i) I understand there are 3 choices for the first path, and then 2 choices for every following movement. E.g. $3*2*2*2*...*(n-1)$ options so there are $3*2^{n-1}$ choices.
However I am struggling to understand the logic for ii)
Any guidance will be greatly appreciated as then I can continue with the follow up questions!
 A: Assume $n = 1$. In this case, there are three cases for the number of flies $k$:


*

*The frog did not move, $k \mod 3 = 0$

*The frog moved left, $k \mod 3 = 1$

*The frog moved right, $k \mod 3 = 2$
In order to arrive at $k \mod 3 = 0$ for $n = 2$, one and only one move can be taken from each of these states: do not move, move right, and move left, respectively. The same is true for $k \mod 3 = 1$ and $k \mod 3 = 2$, so we find three different paths for each of these. A similar reasoning can be used to extend these paths to a length of three, four, etc. In the end, we find that there are $\frac{3^n}{3} = 3^{n-1}$ paths of length $n$ for which the number of caught flies $k$ is divisible by three.
As a hint for (iii): first consider the number of paths $T_{n-1}$ of length $n - 1$ resulting in an even number of flies, and multiply by two, since there are two "even moves"; then consider the number of paths $O_{n-1} = 3^{n-1} - T_{n-1}$ of length $n - 1$ resulting in an odd number of flies, and multiply by one, since there is only one "odd move". This will result in a recurrence relation for the number of paths $T_n$, with $T_1 = 2$. Can you take it from here?
A: Answer heavily collaborated with jvdhooft.
(i) I agree with you.  
(ii) For any path of length $n$, you can make the total number of flies divisible by 3 by making a single correct choice on the last jump.  Therefore, one-third of the number of possible paths, or $3^{n-1}$ have a total number of flies divisible by 3 (assuming we're not using the restriction from (i)).  
(iii) If the number of flies caught a minute ago was even, then there are two ways to have a total count now.  If there number of flies caught a minute ago was odd, there is only way way to get to an even count now.  In other words, $T_n=3^{n-1}+T_{n-1}$ with $T_1=2$.  That gives me $T_2=5$ $T_3=14$ $T_4=41$ $T_5=122$.
(iv) There are five ways to catch an even number of flies in the last two steps (00, 02, 11, 20, and 22), and $T_{n-2}$ ways to have had an even number of flies coming into that, so our answer is $5T_{n-2}$.
(v) Based on (iv), I'm going to say that it's just $F_n=5T_{n-2}$ and $F_2=5$.  $F_5=70$.  
Formally speaking, that's not a recursive sequence because $F_n$ is not defined in terms of previous terms of $F$.  You can make that happen as follows: 
$$F_n=5T_{n-2}=5(3^{n-3}+T_{n-3})=5\cdot 3^{n-3}+5T_{n-3}=5\cdot 3^{n-3}+F_{n-1}$$ but IMHO that's no easier to compute and disguises the elegance of the relationships.  Do as you will.
