# Find generating function for sequence

I am suppose to find generating function for sequence $(e_n)_0^\infty$ where $e_n$ is number of ways how to write a number $n$ as a sum of four natural odd numbers ($e_n$ is basically a number of ordered fours $(\alpha, \beta, \gamma, \delta)$ odd natural numbers that $\alpha + \beta + \gamma + \delta = n$)

I don't know how should I start or "imagine" this problem.

• Would you know how to do it if the numbers didn't have to be odd? Do you know how to do any generating function problems? Do you know what a generating function is? – Gerry Myerson Mar 2 '15 at 12:22
• @GerryMyerson I know generating functions. If numbers didn't have to be odd then I have $n$ numbers. So I need to choose 4 numbers that $\alpha + \beta + \gamma + \delta = n$. So it should be $e_n = \binom{n + 3}{3}$? Now I am not sure how to do it with only odd numbers. – Xoroxoxoxoxoso Mar 2 '15 at 17:15
• You have found $e_n$ (in the don't-have-to-be-odd case), but the question doesn't ask for $e_n$, it asks for the generating function for $e_n$. Do you know how to do that? I mean, do it without knowing that formula for $e_n$? – Gerry Myerson Mar 2 '15 at 22:37
• Are you still here? Any thoughts/questions about the answer you have received? – Gerry Myerson Mar 4 '15 at 11:37
• @GerryMyerson I guess I have figured it out, see my answer. – Xoroxoxoxoxoso Mar 4 '15 at 20:22

I’ll get you started. Consider the product

$$(x_1+x_1^3+x_1^5+\ldots)(x_2+x_2^3+x_2^5+\ldots)(x_3+x_3^3+x_3^5+\ldots)(x_4+x_4^3+x_4^5+\ldots)\;;$$

a typical term has the form $x_1^\alpha x_2^\beta x_3^\gamma x_4^\delta$, where $\alpha,\beta,\gamma$, and $\delta$ are odd positive integers. If you were to drop the subscripts on the indeterminates, that would be $x^{\alpha+\beta+\gamma+\delta}$. And if you were to collect like powers, the coefficient of $x^n$ would be the number of terms $x^{\alpha+\beta+\gamma+\delta}$ with $\alpha+\beta+\gamma+\delta=n$. In other words, it would be $e_n$. Thus,

$$\sum_{n\ge 0}e_nx^n=\left(x+x^3+x^5+\ldots\right)^4\;.$$

Can you take it from here to get the desired generating function?

Well, I guess I have figured that out:

\begin{multline*} \sum_{(\alpha, \beta, \gamma, \delta) \in L^4} x^{\alpha + \beta + \gamma + \delta} = \sum_{\alpha \in L} \sum_{\beta \in L} \sum_{\gamma \in L} \sum_{\delta \in L} x^{\alpha + \beta + \gamma + \delta} = \\ = \sum_{(\alpha, \beta, \gamma) \in L^3} \left(x^{\alpha + \beta + \gamma} \cdot \sum_{\delta \in L} x^\delta\right) = \sum_{(\alpha, \beta, \gamma) \in L^3} \left(x^{\alpha + \beta + \gamma} \frac{x}{1 - x^2}\right) = \\ = \left (\frac{1}{1 - x^2} \right) \sum_{(\alpha, \beta) \in L^2}x^{\alpha + \beta} \cdot \sum_{\gamma \in L} x^\gamma = \left(\frac{x}{1 - x^2}\right)^2 \sum_{\alpha \in L}\left(x^\alpha \sum_{\beta \in L} x^\beta\right) = \\ = \left(\frac{x}{1 - x^2}\right)^3 \sum_{\alpha \in L}x^\alpha = \left(\frac{x}{1 - x^2}\right)^4 = A(x) \end{multline*}

Where $L$ is a set of odd numbers. There will $x^n$ exactly so many times how many are there odd four numbers that $\alpha + \beta + \gamma + \delta = n$ and that is $e_n$-times.

It is basically what @Brian M. Scott was saying.

• Looks good (except for one place where you have written $1/(1-x^2)$ where you meant $x/(1-x^2)$). – Gerry Myerson Mar 4 '15 at 22:56