Given 2 generating functions for the sequences ($a_r$) and ($b_r$), show that $a_r$ = $b_{r+1}$ for each $r$ = 1, 2, ...

236 Views Asked by At

Q: Let $a_r$ be the number of ways of distributing $r$ identical objects into 5 distinct boxes so that boxes 1, 3 and 5 are not empty. Let $b_r$ be the number of ways of distributing $r$ identical objects into 5 distinct boxes so that each of he boxes 2 and 4 contains at least two objects. Show that $a_r = b_{r+1}$ for each $r = 1, 2, ...$.

I have found the generating functions for the sequences ($a_r$) and ($b_r$) to be $x^3 $ $(\frac{1}{1-x})^5$ and $x^4 $ $(\frac{1}{1-x})^5$ respectively. What is exactly $b_{r+1}$ and how do I go about showing that $a_r = b_{r+1}$ for each $r = 1, 2, ...$? I thought of replacing the $r$'s with $r+1$ for the $b_{r+1}$ but doing so still didn't make much sense to me..

1

There are 1 best solutions below

4
On BEST ANSWER

The generating functions should be respectively

$$f(x)=\frac{x^3}{(1-x)^5}\qquad\text{and}\qquad g(x)=\frac{x^4}{(1-x)^5}$$

for the first and second sequences. That is,

$$f(x)=\frac{x^3}{(1-x)^5}=\sum_{n\ge 0}a_nx^n\;,$$

and

$$g(x)=\frac{x^4}{(1-x)^5}=\sum_{n\ge 0}b_nx^n\;.$$

HINT: Note that $g(x)=xg(x)$:

$$\sum_{n\ge 0}b_nx^n=g(x)=\frac{x^4}{(1-x)^5}=x\cdot\frac{x^3}{(1-x)^5}=x\sum_{n\ge 0}a_nx^n=\sum_{n\ge 0}a_nx^{n+1}\;.$$

Now shift the index in that last summation so that the general term has $x^n$ instead of $x^{n+1}$.