What's the number of ways Lior can eat 4 fruits with conditions?

Question

I would appreciate if you could help me understand how to get a correct final answer. . Below, I described the question and my attempt to solve it.

• A friend from class told me the answer is $f(n) = 3f(n-1)-f(n-2)-f(n-3)$.
• I try two different ways to approch this problem. In none of them I get the answer I mentioned above.
  • In "Way 1" I don't know how to solve the recursive formula.
  • In "Way 2" I get a different recursive formula for $f(n)$.

Question

Lior eats $4$ different fruits every day. The fruits are: Banana, strawberry, apple and orange.
Lior will never eat two bananas in a row, she will never eat two oranges in a row, and after an apple she will only eat an apple.

Suppose that on a certain day she eats $n$ fruits. $f(n)$ denote the different ways Lior can eat fruits on this day. Find a recursive formula for $f(n)$

Way 1

"Banana" $=0$ , "Strawberry"$=1$, "Apple" $=2$ and "orange" $=3$.

$(a_1 ,a_2 ,\dots ,a_n )$ describes the order in which Lior ate the fruits.

$f_i(n)$ denote the number of different ways Lior ate fruits s.t $(a_1 ,a_2 ,\dots ,a_{n-1},i )$

$f_0(n) = f_1(n-1)+f_3(n-1) $

$f_1(n) = f_0(n-1)+f_1(n-1)+f_3(n-1) $

$f_2(n) = f_0(n-1)+f_1(n-1)+f_2(n-1)+f_3(n-1) = f(n-1)$

$f_3(n) = f_0(n-1)+f_1(n-1)$

I don't know how to continue from here.

Way 2

"Banana" $=0$ , "Strawberry"$=1$, "Apple" $=2$ and "orange" $=3$.

$(a_1 ,a_2 ,\dots ,a_n )$ describes the order in which Lior ate the fruits.

$g_i(n)$ denote the number of different ways Lior ate fruits s.t $(i ,a_2 ,\dots ,a_{n-1},a_n )$

$f_0(n) = g_1(n-1)+g_2(n-1)+g_3(n-1) $

$f_1(n) = g_0(n-1)+g_1(n-1)+g_2(n-1)+g_3(n-1)= f(n) $

$f_2(n) = g_2(n-1)= 1$

$f_3(n) = g_0(n-1)+g_1(n-1)+g_2(n-1)$

From this I get $f(n) = 3f(n-1)+2 \ne 3f(n-1)-f(n-2)-f(n-3) $

Answer 1

Way 1 and 2 works (other than the error in way 2). To proceed, you could either:

1. Given that you "know" the recurrence, verify it.

2. If you didn't know the recurrence, then like Lulu suggested, find enough small values so that you can guess at it

3. Alternatively, try to force it out like so for way 1:

$\begin{array}{l l l}f(n) & =& f_0 (n) + f_1(n) + f_2(n) + f_3(n) \\ & = & 3f(n-1) + f_1(n-1) - 2f_2(n-1) \\ & = & 3f(n-1) + [f_2(n-1) - f_2(n-2)] - 2f(n-2) \\ & = & 3f(n-1) + [f(n-2) - f(n-3)] - 2f(n-2) \\ & = & 3f(n-1) - f(n-2) -f(n-3) \\ \end{array}$

As for the explanation of each step, you've already made the necessary observations like $f_2(n) = f(n-1)$, so you should be able to work them through.