1
$\begingroup$

Notice: This is an ungraded practice problem. My solution is correct.

Question: How can I solve the problem below using generating functions which make it clear it uses the sum of squares forumla?

Problem: Solve $a_{n+1} - a_n = n^2$, $n \ge 0$, $a_0 = 1$ by the method of generating functions.

My solution:

$$ \begin{array}{r c l} a_{n+1} - a_n & = & n^2 \\ a_{n+1} x^{n+1} - x a_n x^n & = & n^2x^{n+1} \\ \sum_{i = 0}^{\infty}a_{i+1} x^{i+1} - \sum_{i = 0}^{\infty}a_{i+1} x a_i x^i & = & \sum_{i = 0}^{\infty} i^2 x^{i+1} \\ \end{array} $$

$$\text{Let } f(x) = \sum_{i = 0}^{\infty}a_i x^i \text{. Then:}$$

$$ \begin{array}{r c l l} (f(x) - a_0) - xf(x) & = & \sum_{i = 0}^\infty i^2 x^{i+1} \\ f(x) & = & \frac{1}{1-x} (a_0 + \sum_{i = 0}^\infty i^2 x^{i+1}) \\ & = & (1 + x + x^2 + ...) (1 + x^2 + 4x^3 + 9x^4 + ...) \\ & = & 1 + x + 2x^2 +6x^3 + ... & \text{expansion by hand} \end{array} $$

What routes can I take that make it clear that the last line is equivalent to $\sum_{i = 0}^\infty 1 + \frac{i(i-1)(2i-1)}{6}$? It must be done using generating functions.

$\endgroup$
2
$\begingroup$

We obtain \begin{align*} \color{blue}{f(x)}&=\frac{1}{1-x}\left(a_0+\sum_{i=0}^\infty i^2x^{i+1}\right)\\ &=\frac{1}{1-x}\left(1+x\sum_{i=0}^\infty i^2 x^i\right)\\ &=\frac{1}{1-x}+x\left(\sum_{j=0}^\infty x^j\right)\left(\sum_{i=0}^\infty i^2x^i\right)\\ &=\frac{1}{1-x}+x\sum_{n=0}^\infty\left(\sum_{{i+j=n}\atop{i,j\geq 0}}i^2\right)x^n\tag{1}\\ &=\frac{1}{1-x}+x\sum_{n=0}^\infty\left(\sum_{i=0}^n i^2\right)x^n\\ &=\frac{1}{1-x}+\sum_{n=0}^\infty\frac{n(n+1)(2n+1)}{6}x^{n+1}\\ &=\sum_{n=0}^\infty x^n+\frac{1}{6}\sum_{n=1}^\infty(n-1)n(2n-1)x^n\\ &\,\,\color{blue}{=\sum_{n=0}^\infty\left(1+\frac{1}{6}(n-1)n(2n-1)\right)x^n} \end{align*}

The essence is applying the Cauchy product formula in (1): Multiplication of $\sum_{i=0}^\infty c_i x^i$ with $\frac{1}{1-x}$ transforms the coefficient $c_i \to \sum_{i=0}^n c_i$, here with $c_i=i^2$.

$\endgroup$
  • $\begingroup$ I didn't know I could go from $$\sum_{i=0}^\infty i^2 x^i$$ to $$\sum_{i=0}^\infty\frac{i(i+1)(2i+1)}{6}x^i$$ That must be what I was missing (I haven't seen the in-between steps you have posted before). $\endgroup$ – wybkqqnob Oct 21 '18 at 22:56
  • $\begingroup$ @wybkqqnob: You're welcome. Good to see the answer is useful. $\endgroup$ – Markus Scheuer Oct 22 '18 at 6:34

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.