Finding a closed form expression for $\sum_{k=0}^n(k^2+3k+2)$ using generating functions

951 Views Asked by At

First of all, i know that there is already a similar question (Closed form expression for $\sum_{k=0}^{n}(k^2 + 3k + 2)$) regarding my equation in this forum, but my question is only about verification of my thought process because i am quite new to the concept of generating functions.

I have the following equation which i can rewrite to:

\begin{equation} \sum_{k=0}^n(k^2+3k+2) = \sum_{k=0}^n k^2 + 3\sum_{k=0}^n k + \sum_{k=0}^n 2 \end{equation}

My idea was now to apply generating functions to each of the sums which will give me the same sequences as the sums would generate: \begin{equation} \frac{(1+x)x}{(1-x)^3} + \frac{3x}{(1-x)^2} + \frac{2}{1-x} \end{equation}

And now simplify it and translate it back to a simple sum as follows: \begin{equation} \frac{2}{(1-x)^3} \leftrightarrow \sum_{k=1}^n k(k+1) \end{equation}

Is this a sufficient and correct way of using the concepts of generating functions to get a closed form expression from the given sum or did i miss out on a crucial concept?

1

There are 1 best solutions below

2
On BEST ANSWER

Yes, this approach of splitting into three sums is valid, but you forgot the $\sum_{k=0}^n$. Here's a correct solution. Let $a_n=\sum_{k=0}^n(k^2+3k+2)$. Then \begin{align} \sum_{n=0}^\infty a_n x^n &= \sum_{n=0}^\infty \left(\sum_{k=0}^n(k^2+3k+2)\right) x^n\\ &= \sum_{k=0}^\infty (k^2+3k+2) \sum_{n=k}^\infty x^n\\ &= \sum_{k=0}^\infty (k^2+3k+2) \frac{x^k}{1-x}\\ &= \frac{1}{1-x}\left(\sum_{k=0}^\infty k^2 x^k+3\sum_{k=0}^\infty kx^k+2\sum_{k=0}^\infty x^k\right)\\ &= \frac{1}{1-x}\left(\frac{x(x+1)}{(1-x)^3}+\frac{3x}{(1-x)^2}+\frac{2}{1-x}\right)\\ &= \frac{1}{1-x}\cdot\frac{2}{(1-x)^3}\\ &= \frac{2}{(1-x)^4}\\ &= 2\sum_{n=0}^\infty \binom{n+3}{3} x^n, \end{align} so $$a_n = 2 \binom{n+3}{3} = \frac{(n+3)(n+2)(n+1)}{3}.$$ More generally, note that if $B(x)=\sum_{n=0}^\infty b_n x^n$, then the generating function for the partial sums $\sum_{k=0}^n b_k$ is $B(x)/(1-x)$.