2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Gerry Myerson Mar 2 '15 at 12:22
  • $\begingroup$ @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. $\endgroup$ – Xoroxoxoxoxoso Mar 2 '15 at 17:15
  • 1
    $\begingroup$ 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$? $\endgroup$ – Gerry Myerson Mar 2 '15 at 22:37
  • $\begingroup$ Are you still here? Any thoughts/questions about the answer you have received? $\endgroup$ – Gerry Myerson Mar 4 '15 at 11:37
  • $\begingroup$ @GerryMyerson I guess I have figured it out, see my answer. $\endgroup$ – Xoroxoxoxoxoso Mar 4 '15 at 20:22
4
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

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

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.