Deriving a (tricky, I think?) recurrence relation

Question

I'm having trouble trying to derive a recurrence relation for a problem I'm looking at.

"Let $h_n$ be the number of ways of packing a bag with $n$ fruits (either apples, oranges, bananas, or pears), in which there are an even number of apples, at most two oranges, a multiple of three number of bananas, and at most one pear. Find an explicit formula for $h_n$."

I want to solve by finding a recurrence relation and determining the generating function for the sequence $h_n$.

Not really sure where to get started. Any hints would be nice. I've tried looking at $h_n$ in terms of $h_{n-6}$.

EDIT: I think I found the first 5 elements of the sequence:

$h_0=1, h_1=2, h_2=3,h_3=4,h_4=5$

Answer 1

If you look at the generating function, you can discover a sneaky way to solve this. The generating function is $$\sum h_nx^n=\overbrace{(1+x^2+x^4+\cdots)}^\text{apples}\cdot\overbrace{(1+x+x^2)}^\text{oranges}\cdot\overbrace{(1+x^3+x^6+\cdots)}^\text{bananas}\cdot\overbrace{(1+x)}^\text{pears}.$$ Rewriting the non-polynomial terms as infinite geometric series gives $$\sum h_nx^n=\frac{1}{1-x^2}\cdot(1+x+x^2)\cdot\frac{1}{1-x^3}\cdot(1+x) = \frac{1}{(1-x)^2}.$$

In other words, $h_n$ is the number of ways to pack a bag with $n$ fruits using any number of apple-or-pear-fruits (for original-problem bags with a pear, this number is odd) and banana-or-orange-fruits (the multiple of three from the original bananas, plus zero, one, or two original-problem oranges).

The number of ways to pack a bag with $n$ fruits, using two kinds of fruit is $n+1$ ($k$ of the first fruit and $n-k$ of the second, for any $k$ between $0$ and $n$).

Answer 2

Suppose you let $a_k$ be the number of ways of picking $k$ apples so that there are an even number of applies (i.e. $a_k = 0$ if $k$ is odd and $a_k = 1$ if $k$ is even). Let $o_k$ be the number of ways of picking $k$ oranges so that there are at most two oranges (i.e. $o_k = 0$ if $k > 2$ and $o_k = 1$ if $k \leq 2$). Now consider the corresponding generating series $$a(x) = \sum_{k=0}^{\infty} a_k x^k = 1 + x^2 + x^4 + \cdots = \frac{1}{1 - x^2}$$ and $$o(x) = \sum_{k=0}^{\infty} o_k x^k = 1 + x + x^2.$$ (I'll leave you to work out the generating functions $b(x)$ for bananas and $p(x)$ for pears.)

Then $f(x) = a(x) o(x) b(x) p(x) = \sum_{n=0}^{\infty} h_n x^n$ is the generating function for fruits.