3
$\begingroup$

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$

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1; very nice. Your work shows the importance of finishing a calculation and simplifying it, as it may reveal something hidden that becomes (in hindsight) obvious. $\endgroup$ – Michael Joyce Apr 10 '14 at 16:42
3
$\begingroup$

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.

$\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.