Let's consider generating function $$F(x) = (1+x)^r = \sum_{n=0} \binom{r}{n} x^n$$ And another generating function $$G(x) = (1+x^2)^r = \sum_{n=0} \binom{r}{n}x^{2n}$$ Please note those 2 functions differs only on $x^k$

After that let's take definition of binomial $$\binom{r}{n} = \frac{r^{\underline{n}}}{n!}$$ and apply it to our function $F(x)$ and $G(x)$ first.

$$F(x)=(1+x)^r=\sum_{n=0}^\infty r^{\underline n} \frac{x^n}{n!}$$ $$G(x)=(1+x^2)^r=\sum_{n=0}^\infty r^{\underline n} \frac{x^{2n}}{n!}$$

Whole question is about multiplying those functions.

To multiply $F(x)$ and $G(x)$ we have to have two function of form $\sum_{n=0}^\infty a_n x^n$, but our G(x) has form $\sum_{n=0}^\infty a_n x^{2n}$ So idea here is to make it right form, obviously.

Here i have doubts: should i treat this function as exponential generating function or ordinary generating function?

Because in first case it's seems like i'm iterating over sequence $\langle r^{\underline n} \rangle$ And in second case, if i want to make "correct" ordinary generating function i have to take $x=\sqrt{x}$ and apply it to function, it will give me obviously $G(\sqrt{x})=G_2(x)=(1+x)^r=\sum_{n=0}^\infty x^n$, but now $F(x)G(x) \neq F(x)G_2(x)$, so it doesnt seem like a good solution.

On the side note, $$F(x)G(x) = \sum_{n=0}^\infty ( \sum_{k=0}^n \binom{r}{k} \binom{r}{n-2k}) x^n$$

So my question is: how to work with such generating function? How to multiply them and how to change them to "right" form?

(Second side question : can we multiply our functions if both are in form $\sum_{n=0}^\infty a_n x^{kn}$ for some k being an integer/real number?)


Whether you are contemplating OGFs or EGFs at this point is irrelevant -- multiplication here is simply as formal power series, without regards to interpretation.

There are a couple of ways that you can think about this; here's one way.

Note that when you multiply to power series $\sum a_nx^n$ and $\sum b_nx^n$, the result is $$ \sum_{n=0}^{\infty}c_nx^n,\qquad c_n:=\sum_{k=0}^{n}a_kb_{n-k}. $$ In this case, you can think of $$ a_n=\begin{cases}\binom{r}{n/2} & \text{if $n$ is even}\\0 & \text{else}\end{cases},\qquad b_n=\binom{r}{n}. $$ This means that your $c_n$ in this case will be $$ \sum_{k=0}^{n}a_kb_{n-k}=\sum_{j=0}^{\lfloor n/2\rfloor}a_{j}b_{n-2j}=\sum_{j=0}^{\lfloor n/2\rfloor}\binom{r}{j}\binom{r}{n-2j} $$ where we have noticed that all terms with odd $k$ are $0$, and reindexed using $k=2j$.

  • $\begingroup$ Thanks for your solution, it's very nice, but i won't accept your question yet, cause i'm interested at another question too :) and maybe other methods of it to... $\endgroup$ – Krzysztof Lewko Apr 3 '14 at 13:24
  • $\begingroup$ Been thinking about this next day and i think it's the best solution out there. Thanks :) $\endgroup$ – Krzysztof Lewko Apr 5 '14 at 8:37

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.