# Recurrence relation- Eating fruits

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:)

• I would think of conditioning on (i.e. fixing values) of the first two elements – gt6989b May 14 at 14:34

## 1 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 