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 ?
Best Answer
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)$?