2
$\begingroup$

If we have some generating function $G(x)$ that generates terms indefinitely, is there a way to translate it to be a finite generating function?

For example if I only want to generate the first $k$ terms of a sequence, can I do $G(x) - x^kG(x)$ or something similar? This isn't the right answer but it's where my thought process is. Trying to find some way to "start" the recurrence at a later point so that when I subtract one infinite generating function from the other, all the terms past $k$ drop out.

$\endgroup$
  • $\begingroup$ I'm not sure what you are asking. Are you looking for a general way to compute a $k$-th order Taylor polynomial? $\endgroup$ – Marc Paul Jan 14 '16 at 22:34
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice exposition! (+1) $\endgroup$ – Markus Scheuer Aug 18 '16 at 17:54
  • $\begingroup$ Thank you for the kind remark. As you have recently presented posts where the Egorychev method is implemented using formal power series only (as opposed to contour integrals) you may want to look at this MSE post. I think it would gain from a formal power series solution. What has been posted there can be streamlined and simplified. $\endgroup$ – Marko Riedel Aug 18 '16 at 18:05
  • $\begingroup$ Done. Thanks! :-) $\endgroup$ – Markus Scheuer Aug 18 '16 at 19:16
  • $\begingroup$ I think you should replace $f(v)$ with $f(wv)$ in your last line. I've added a small supplement to your addendum. Regards, $\endgroup$ – Markus Scheuer Aug 19 '16 at 12:52
4
$\begingroup$

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^n\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^n\right)t^n\\ &=\sum_{k=0}^n g_k x^n \end{align*}

| cite | improve this answer | |
$\endgroup$

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.