0
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.