1
$\begingroup$

The title is probably somewhat unclear, sorry if it is..

Let $F$ be the generating function of the sequence $(a_n)_{n=0}^{\infty}$

Use $F$ to express the generating function for $(b_n)_{n=0}^{\infty}$ that is defined by $b_n = \sum_{k=0}^{n} 3^k\cdot a_k$ .

I have went through my notes on generating functions, and most of it was about using this technique for solving some combinatorical problems. I would be happy to have some explanation on how to approach the above problem and other problems of this sort.

Thanks!

$\endgroup$
3
  • $\begingroup$ Are you familiar with Cauchy products of series? $\endgroup$
    – Clement C.
    Commented May 25, 2014 at 19:18
  • $\begingroup$ This was briefly presented to us as the "Convolution Formula", and strangely enough, was not covered by any previous homework we got, but I am willing to understand it thoroughly if you (or someone else) have the patience :) $\endgroup$
    – Boris Ablamunits
    Commented May 25, 2014 at 19:28
  • $\begingroup$ See my answer below, then :) $\endgroup$
    – Clement C.
    Commented May 25, 2014 at 19:29

1 Answer 1

Reset to default
2
$\begingroup$

Recall that $$ \frac{3}{3-X} = \sum_{n=0}^\infty 3^{-n} X^n. $$ The product $\frac{3F(X)}{3-X}$ can be written, using the properties of Cauchy product, as $$ \frac{3F(X)}{3-X} = \left(\sum_{n=0}^\infty a_n X^n\right)\left(\sum_{n=0}^\infty 3^{-n} X^n\right) = \sum_{n=0}^\infty c_n X^n $$ with $c_n=\sum_{k=0}^n a_k 3^{-(n-k)} = 3^{-n} b_n$. Let us write $G$ for the generating function defined by $$ G(X) = \sum_{n=0}^\infty b_n X^n $$ Then $$G\!\left(\frac{X}{3}\right) = \sum_{n=0}^\infty 3^{-n}b_n X^n = \sum_{n=0}^\infty c_n X^n = \frac{3F(X)}{3-X}.$$ (or, equivalently, $G(X) = \frac{F(3X)}{1-X}$)

$\endgroup$
6
  • $\begingroup$ As a sanity check: $G(0) = b_0 = 3^0 a_0 = a_0 = F(0) = \frac{F(3\cdot 0)}{1-0}$, and also $G^\prime(0) = b_1 = 3a_1 + a_0 = 3F^\prime(0)+F(0)$, which is also what we find by differentiating the expression $\frac{F(3X)}{1-X}$ and evaluating it at $X=0$. $\endgroup$
    – Clement C.
    Commented May 25, 2014 at 19:39
  • $\begingroup$ up until $c_n=\sum_{k=0}^n a_k 3^{-(n-k)} = 3^{-n} b_n$ I think I followed you alright. Could you please explain this point and what follows with more detail? Thanks again for your time. $\endgroup$
    – Boris Ablamunits
    Commented May 25, 2014 at 19:53
  • $\begingroup$ This is the property of Cauchy products which is used: $$\left(\sum_{n=0}^\infty a_n X^n\right)\left(\sum_{n=0}^\infty b_n X^n\right) = \sum_{n=0}^\infty \left(\sum_{k=0}^n a_k b_{n-k}\right) X^n$$ Applying this equality gives you what I wrote. To see why this is true, either look at the Wikipedia page (which I fing confusing, since it deals with issues of convergence one does not have for formal power series), or try to prove it by hand: the coefficient of $X^n$ in the product comes from all terms $a_j b_iX^{i+j}$ from the left-hand side, where $i+j=n$. $\endgroup$
    – Clement C.
    Commented May 25, 2014 at 20:00
  • $\begingroup$ Ah yes - it took me a few more minutes to set my mind around this, and solving it myself by following your way helped. Just one last question that is bugging me - is there any guideline I could use to get the idea where to start from? How did you know the place to start was $\frac{3}{3-X} = \sum_{n=0}^\infty 3^{-n} X^n$ ? From there everything seemed pretty logical and nice! $\endgroup$
    – Boris Ablamunits
    Commented May 25, 2014 at 20:44
  • $\begingroup$ Once you recognize something looking like the coefficient $c_n$ of a Cauchy product in $sum_{k=0}^n 3^k a_k$, you get that the coefficient $d_n$ of one of the series must be something like $3^{\pm n}$, to get $d_{n-k}\propto3^k$. Then, trying $3^n$ and $3^{-n}$ tells you which one works... And then you can compute the closed-form expression of the resulting generating function. $\endgroup$
    – Clement C.
    Commented May 25, 2014 at 20:50

You must log in to answer this question.

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