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$
Best Answer
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$).