How to get series coefficient for $\frac{1}{(1-x)^3}$?

Question

I was trying to use generating functions to get a closed form for the sum of first $n$ positive integers.

So far I got to $G(x) = \frac{1}{(1-x)^3}$ but I don't know how to convert this back to the coefficient on power series.

Answer 1

You can use $\frac 1{1-x}=\sum_{i=0}^\infty x^i$ and take two derivatives $$\frac {d^2}{dx^2}\frac 1{1-x}=\frac 2{(1-x)^3}=\frac {d^2}{dx^2}\sum_{i=0}^\infty x^i=\sum_{i=0}^\infty(i+2)(i+1)x^i\\=1+3x+6x^2+10x^3+\ldots$$ which is off by $1$ in the index.

Answer 2

Using Binomial series,

for $|-x|<1,$

$$(1-x)^{-3}=\sum_{r=0}^\infty\dfrac{(-3)(-2)\cdots\{-3-(r-1)\}}{r!}(-x)^r$$

Now $\dfrac{(-3)(-3-1)\cdots\{-3-(r-1)\}}{r!}=(-1)^r\dfrac{(r+2)(r+1)\cdots3}{r!}=(-1)^r\dfrac{(r+1)(r+2)}2$

Answer 3

Since $\frac{1}{1-x}=1+x+x^2+x^3+\ldots$ for any $x\in(-1,1)$, we have

$$ [x^n]\frac{1}{(1-x)^k} = \begin{array}{c}\small\text{number of ways for writing }n\\\small\text{as a sum of }k\small\text{ natural numbers}\end{array} $$ and the RHS is given by stars and bars. In general we have $$ \frac{1}{(1+x)^{m+1}} = \sum_{n\geq 0}\binom{m+n}{n}x^n.$$

Answer 4

Let $\frac{1}{(1-x)^3}=\sum_{i=0}^{\infty}a_ix^i$, then $$1=(1-3x+3x^2-x^3)\sum_{i=0}^{\infty}a_ix^i=\sum_{i=0}^{\infty}a_ix^i-\sum_{i=0}^{\infty}3a_ix^{i+1}+\sum_{i=0}^{\infty}3a_ix^{i+2}-\sum_{i=0}^{\infty}a_ix^{i+3}$$

From this we get (by comparing LHS and RHS):

• $1=a_0$
• $0=a_1-3a_0\Rightarrow a_1=3$
• $0=a_2-3a_1+3a_0\Rightarrow a_2=6$
• $0=a_{n+3}-3a_{n+2}+3a_{n+1}-a_n$, for $n\geq 0$

Now, consider the difference between each coefficient $$a_0,a_1,a_2,a_3,a_4,a_5,\dots\\a_1-a_0,a_2-a_1,a_3-a_2,a_4-a_3,a_5-a_4,\dots\\a_2-2a_1+a_0,a_3-2a_2+a_1,a_4-2a_3+a_2,a_5-2a_4+a_3,\dots\\0,0,0,0,0,\dots$$

The last line is $0$, since $0=a_{n+3}-3a_{n+2}+3a_{n+1}-a_n$. This means that $a_n$ is a polynomial of degree $2$, so that $$a_n=c_2n^2+c_1n+c_0$$

To find $c_2,c_1,c_0$ note:

• $a_0=1\Rightarrow c_0=1$
• $a_1=3\Rightarrow 2=c_2+c_1$
• $a_2=6\Rightarrow5=4c_2+2c_1$

This gives:

• $c_0=1$
• $c_1=\frac{3}{2}$
• $c_2=\frac{1}{2}$

So: $$a_n=\frac{n^2}{2}+\frac{3n}{2}+1=\frac{(n+1)(n+2)}{2}$$