Product of generating functions

Question

Let $f(x) = \sum_{i=0}^\infty a_ix^i$ and $g(x) = \sum_{i=0}^\infty b_ix^i$ where $a_n = 1$ and $b_n = 2^n$ for all natural numbers $n$

What are the first three terms of the sequence generated by $f(x)g(x)$ ?

So I know that $f(x)$ will generate $\{1,1,1,1,1,.... \}$ and $g(x)$ will generate $\{1,2,4,8,16,32,64,....... \}$

The first term $c_0$ of the sequence $f(x)g(x)$will be $1 \times 1 = 1$ and the second term $c_1$ will be $a_0 \times b_1 + a_1 \times b_0 = 1 \times 2 + 1 \times 1 = 3$ and finally $c_2 = 1 \times 4 + 1 \times 2 + 1 \times 1 = 7$

Now what is the general formula for the sequence generated by $f(x)g(x)$, assume that it generates $\{c_0,c_1,c_2,c_3,..........\}$

If I calculates $c_3$ it would be easier to see that pattern, $c_3 = 8 + 4 + 2 + 1 = 15$

and so the sequence is $\{1,3,7,15,31,.................... \}$

It is basically $\{1,2^{2}-1,2^3-1,2^4-1,.... \}$ and so it is $\{1,a^2-1,a^3-1,a^4-1,.... \}$ where $a=2$, Is this general formula correct ?

I mean what is the formula , I just know the pattern here. So is the formula just $$c_k = 2^k-1$$ where $k>1$

What function generates the sequence $\{c_0,c_1,c_2,..... \}$?

Well I know that $\frac{1}{1-2x}$ generates the sequence $\{1,2,2^2,2^3,... \}$ and that $\frac{-1}{1-x}$ generates $\{-1,-1,-1,.... \}$ but adding these two functions will gives us the sequence $\{0,1,2^2-1,2^3-1 \}$

And what should I do to eliminate that zero, multiply by $x$ will add more zero, what should do I do eliminate one zero ?

Answer 1

You want the Cauchy product: the coefficient of $x^n$ in $f(x)g(x)$ is

$$\sum_{k=0}^na_kb_{n-k}=\sum_{k=0}^n1\cdot2^{n-k}=\sum_{k=0}^n2^{n-k}=\sum_{k=0}^n2^k=2^{n+1}-1=c_n\;.$$

The generating function is simply $f(x)g(x)$; are the generating functions $f(x)$ and $g(x)$?

Answer 2

$f(x)=\frac{1}{1-x}$, $g(x)=\frac{1}{1-2x}$, $f(x)g(x)=\frac{1}{(x-1)(2x-1)}$

Answer 3

In general:

$\begin{align} \left( \sum_{n \ge 0} a_n z^n \right) \cdot \left( \sum_{n \ge 0} b_n z^n \right) = \sum_{n \ge 0} \left(\sum_{0 \le k \le n} a_k b_{n - k} \right) z^n \end{align}$

In your particular case, $a_n = 1$, switching the product around:

$\begin{align} \left( \sum_{n \ge 0} b_n z^n \right) \cdot \left( \sum_{n \ge 0} z^n \right) &= \sum_{n \ge 0} \left(\sum_{0 \le k \le n} b_k \right) z^n \\ \frac{1}{1 - 2 z} \cdot \frac{1}{1 - z} &= \sum_{n \ge 0} \left(\sum_{0 \le k \le n} 2^k \right) z^n \\ \frac{1}{1 - 3 z + z^2} &= \sum_{n \ge 0} (2^{n + 1} - 1) z^n \end{align}$

The observation that:

$\begin{align} g(z) &= \sum_{n \ge 0} b_n z^n \\ \frac{g(z)}{1 - z} &= \sum_{n \ge 0} \left(\sum_{0 \le k \le n} b_k\right) z^n \end{align}$

is quite useful.