Coefficient of Generating Functions Question

Question

I did Part (a) and for Part (b) I found the coefficient of each of the separate series in (a). How do I combine these two together to get the answer to (b). And for Part(c), how can I do this another way?

So Far,

Answer 1

For b) The formula for a product is

$$ [x^n] \left( \sum_{i} a_i x^i \right)\left( \sum_j b_jx^j \right) = \sum_{i + j = n} a_ib_j. $$

In your case,

$$ [x^n] \left( \sum_{i} \binom{i+k-1}{i}x^{2i} \right)\left( \sum_{j} \binom{j+k-1}{j}x^{j} \right) = \sum_{2i + j = n} \binom{i + k - 1}{i} \binom{j + k - 1}{j} .$$

We then rewrite the sum as $\sum_{i = 0}^{N} \cdots$ where $N$ is such that $j = n - 2i$ is always $\ge 0$. So we must have $i \le \lfloor n/2 \rfloor$ (think about it). Then with the substitution $j = n - 2i$, we have

$$ \sum_{i = 0}^{\lfloor n/2 \rfloor} \binom{i + k - 1}{i} \binom{(n - 2i) + k - 1}{(n - 2i)}. $$

This is part (b).

For part (c), what you want to do is write $$(1 - x^2)^{-k}(1 - x)^{-k} = (1 - x)^{-k}(1 + x)^{-k}(1 - x)^{-k} = (1 - x)^{-2k}(1 + x)^{-k}.$$

Then, by exactly the same method, $[x^n](1 - x)^{-2k}(1 + x)^{-k}$ will give you the left hand side of the identity in (c). In fact, it is tiny bit easier because there's no $x^2$.