Making an infinite generating function a finite one

Solution 1:

The answer from @MarkoRiedel is nice and inspiring. It presents a useful technique to select the first $n$ terms of a series. Here I'd like to provide a small supplement and take a somewhat closer look at his addendum.

Situation: Given a series $G(x)=\sum_{k=0}^\infty g_kx^k$. Find a formula to extract the first $n$ terms of $G(x)$: \begin{align*} \sum_{k=0}^ng_kx^k\tag{1} \end{align*}

In the following we use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. We obtain a formula in some steps. We start with

Summing up elements

Multiplication of a series $G(x)$ with $\frac{1}{1-x}$ results in summing up the coefficients of $G(x)$. \begin{align*} \frac{1}{1-x}G(x)&=\left(\sum_{k=0}^\infty g_kx^k\right)\left(\sum_{l=0}^\infty x^l\right)\\ &=\sum_{n=0}^\infty\left(\sum_{{k+l=n}\atop{k,l\geq 0}}g_k\right)x^n\\ &=\sum_{n=0}^\infty\left(\sum_{k=0}^n g_k\right) x^n\tag{2} \end{align*}

Shift of variable

The coefficient in (2) is a first step, but it is separated from $x$. Since we want to obtain the expression stated in (1), we use a trick. We shift the meaning of the variable $x$ and make it part of the coefficient. In order to do so we introduce a new variable $t$ and consider \begin{align*} G(tx)=\sum_{k=0}^\infty g_k x^k t^k \end{align*} The shift is not fully done, but it is a step in a useful direction. Now we sum up the coefficients, but by multiplying with $ \frac{1}{1-t}$ instead of multiplying it with $\frac{1}{1-x}$. We obtain \begin{align*} \frac{1}{1-t}G(xt)=\sum_{n=0}^\infty\left(\sum_{k=0}^n g_k x^k\right)t^n\tag{3} \end{align*}

Coefficient extraction

Now the downgrade of $x$ in (3) is complete. We can extract the coefficient of $t^n$ and obtain finally \begin{align*} [t^n]\frac{1}{1-t}G(xt)&=[t^n]\sum_{n=0}^\infty\left(\sum_{k=0}^n g_k x^k\right)t^n\\ &=\sum_{k=0}^n g_k x^k \end{align*}

Solution 2:

Edited Jan 27 2018. Answer by M.Scheuer is sufficient.