2
$\begingroup$

I was going through Alan Tucker's Applied Combinatorics when I came across this exercise in Chapter 6: Generating Functions, page $281$

If $h(x)$ is the ordinary generating function for $a_r$, find the generating function for $s_r=\sum_{k=r+1}^\infty a_k$ , assuming all $s_r$'s are finite and $a_r\to 0$ as $r\to \infty$.

We have $h(x)=\sum_{r=0}^\infty a_rx^r $ and we can define $f(x)=\sum_{r=0}^\infty s_rx^r$ to be the generating function we wish to identify. Thus,

$$f(x)=\sum_{r=0}^\infty \left(\sum_{k=r+1}^\infty a_k\right)x^r=\sum_{r=0}^\infty \left(h(1)-\sum_{k=0}^r a_k\right)x^r$$

Expanding, $$f(x)=h(1)\sum_{r=0}^\infty x^r -\sum_{r=0}^\infty\left(\sum_{k=0}^r a_k\right)x^r=\frac{h(1)}{1-x}-\frac{h(x)}{1-x}=\frac{h(1)-h(x)}{1-x}$$

Could someone please check if I'm right? Or offer another solution if I'm wrong? Thanks in advance!

$\endgroup$
2
  • 1
    $\begingroup$ I checked it, seems to be true. $\endgroup$
    – on1921379
    Aug 11, 2022 at 7:07
  • $\begingroup$ @on1921379 Thank you for checking! $\endgroup$
    – Cathedral
    Aug 11, 2022 at 8:51

1 Answer 1

1
$\begingroup$

Yes, it is correct. Another approach is to interchange the order of summation: \begin{align} \sum_{r=0}^\infty \left(\sum_{k=r+1}^\infty a_k\right) x^r &= \sum_{k=1}^\infty a_k \sum_{r=0}^{k-1} x^r \\ &= \sum_{k=1}^\infty a_k \frac{1-x^k}{1-x} \\ &= \frac{\sum_{k=1}^\infty a_k - \sum_{k=1}^\infty a_k x^k}{1-x} \\ &= \frac{(h(1) - a_0) - (h(x) - a_0)}{1-x} \\ &= \frac{h(1) - h(x)}{1-x} \end{align}

$\endgroup$
1
  • $\begingroup$ I quite like this answer. Thank you! $\endgroup$
    – Cathedral
    Sep 6, 2022 at 3:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .