Question: $h_n$ is the number of nonnegative integer solutions to
$$e_1*1^2 + e_2*2^2 + e_3*3^2 + \cdots + e_n*n^2 = n$$
where $n\ge0$. What would be the ordinary (not exponential) generating function $G(x)$ expressed as a product for the sequence $\{h_n\}$ from $n=0$ to $n=\infty$? After that, prove your $G(x)$ answer is correct.
When I did this, I was able to express my $G(x)$ as a sum, but I was not able to express it in the required form. Also, I believe the way to prove this would be either using induction or some combinatorics proving method, but I am not sure how I would apply that.
Could someone help out please?
Thanks
Best Answer
The general framework for using generating functions to count the number of solutions to integer equations is this. If you want to count the number of solutions to $$ x_1+x_2+x_3+\dots=n, $$ satisfying the constraints $$ x_1\in S_1,x_2\in S_2,x_3\in S_3,\dots $$ then the generating function is $$ \left(\sum_{i\in S_1} x^i\right)\left(\sum_{i\in S_2} x^i\right)\left(\sum_{i\in S_3} x^i\right)\cdots $$ Now, in your case, you do not have just a sum of variables, you have a variables times certain coefficiets: $$ 1x_1+4x_2+9x_3+\dots=n $$ (Notice I have let the sum extend infinitely, which does not affect the number of solutions, but does let us apply this method). However, if you instead replace each summand $k^2x_k$ with a new variable $y_k$, then the equation is $$ y_1+y_2+y_3+\dots=n, $$ which fits in our framework. However, whereas the $x_k$ could be any nonnegative integer, the fact that $y_k=k^2x_k$ means the $y_k$ must obey certain restraints. What are they?