0

I need to find the coefficient of $x^8$ in the following using generating functions:

$$\frac{(1+x)^2}{1-3x} $$

I attempted to write out three different generating functions adding together to give the numerator with a common denominator of $1-3x$. But this has led me no where. Any hints would be appreciated, even in the general way.

mle
  • 2,287
H5159
  • 969

2 Answers2

2

Use the geometric series to expand the denominator (assuming $|x|<\frac13$) and then multiply with $(1+x)^2$. More specifically $$\begin{align*}\frac{(1+x)^2}{1-3x}&=(x^2+2x+1)\cdot\frac{1}{1-3x}=(x^2+2x+1)\sum_{n=0}^{\infty}(3x)^n=\\&=(x^2+2x+1)\left(1+3x+(3x)^2+\ldots+(3x)^6+(3x)^7+(3x)^8+\ldots\right)=\\&=\ldots+x^2\cdot(3x)^6+2x\cdot(3x)^7+(3x)^8+\ldots=\\&=\left(3^6+2\cdot3^7+3^8\right)x^8+\ldots\end{align*}$$ where in the last equations I wrote only the terms concerning $x^8$. So the requested coefficient is equal to $$3^6+2\cdot3^7+3^8$$ assuming $|x|<\frac13$.

Jimmy R.
  • 35,868
  • Ahh, how simple that was; yet I could not think of that on my own. Makes me feel pretty stupid. Thank you. – H5159 Mar 23 '14 at 22:34
  • 1
    @Frumpy You are welcome! Do not worry, earlier today, I could not solve a probability exercise that someone else solved with a very nice way, so today I feel pretty stupid too... – Jimmy R. Mar 23 '14 at 22:38
1

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle #1 \right\rangle} \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left( #1 \right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ \begin{align} \mbox{With}\ \verts{x} < {1 \over 3}\,;\qquad{\pars{1 + x}^{2} \over 1 - 3x}&= \pars{1 + 2x + x^{2}}\sum_{n = 0}^{\infty}\pars{3x}^{n} =\sum_{n = 0}^{\infty}\bracks{3^{n}x^{n} + 2\times 3^{n}x^{n + 1} + 3^{n}x^{n + 2}} \end{align}

Solution: $$ 3^{8} + 2\times 3^{7} + 3^{6} = 3^{6}\times 16 = \color{#00f}{\Large 11664} $$

Felix Marin
  • 89,464