Recurrence relation- Eating fruits

combinatoricsrecurrence-relations

Joe eats bananas, oranges, apples and strawberries every day.
Joe would never eat 2 bananas or 2 oranges in a row, and after eating an apple he would only eat apples.
Let $f(n)$ be the number of ways Joe can eat $n$ fruits a day (the order of the fruits matters).

I need to find the recurrence relation for $f(n)$.

I tried to separate the cases according to the last fruit he ate,
so if it was an apple there are $f(n-1)$ options,
if it was a strawberry there are $f(n-1)-f(n-2)$ options (because there are $f(n-1)$ options without any limitation and the we have to subtract the cases that he ate an apple before the strawberry which are $f(n-2)$) ,
I am stuck about the banana and similarly for the orange.

Would appreciate any help how to proceed:)

Best Answer

Hint: Let $f(n)$ be the number of ways to eat $n$ pieces of fruit ending with an apple. Because we get stuck on apples, let $g(n)$ be the number of ways to eat $n$ pieces of fruit ending with a banana. There are also $g(n)$ ways to eat $n$ pieces of fruit and ending with an orange. Let $h(n)$ be the number of ways to eat $n$ pieces of fruit ending with strawberries. You should be able to write coupled recurrences for $g(n),h(n)$. Then the total number of ways of eating $n$ pieces of fruit is $f(n)+2g(n)+h(n)$

An apple can go after anything, so $f(n)=f(n-1)+2g(n-1)+h(n)$. A banana can go after an orange or a strawberry, so $g(n)=g(n-1)+h(n-1)$. A strawberry can go after anything but an apple, so $h(n)=2g(n-1)+h(n-1)$

A spreadsheet with the result is below
enter image description here