Solve the recursion $a_n = a_{n-1} + n-1$ by using generating functions .

88 Views Asked by At

For $a_0 = 0$, solve $a_n = a_{n-1} + n-1$. My sequence is : $$ 0x^0 + 0x^1+1x^2+3x^3+6x^4+10x^5+15x^6+\ldots $$ Lets call that $F(x)$: now multiply $F(x)$ by $x$ and subtract the result from $F(x)$ $$ F(x)-F(x)\cdot x = 1\cdot x^2 + 2\cdot x^3 + 3\cdot x^4 + 4\cdot x^5 + \dots $$ It seems that $$ F(x)-F(x)\cdot x=\frac{x^2}{(1-x)^2} $$ and this implies $$ F(x)=\frac{x^2}{(1-x)^3} $$ but could not find what to do after that ..

And the question is important because I am trying to understand the process of solving recurrence relations by using generating functions , this is not from my homework Though I don't know how to convince you .

1

There are 1 best solutions below

4
On BEST ANSWER

You are almost done, now you can use partial fractions decomposition to write $$ F(x)=\frac{1}{(1-x)^3}-\frac{2}{(1-x)^2}+\frac{1}{1-x}, $$ and extract coefficient of each term separately. Last one is just geometric series $1+x+x^2+ \dots$ for $|x|<1$. For the other ones, notice that $\left(\frac{1}{1-x}\right)'=\frac{1}{(1-x)^2}$ and $\left(\frac{1}{(1-x)^2}\right)'=\frac{2}{(1-x)^3}$, so you can get coefficients of these by differentiating the corresponding series. Can you finish it now?

Plus, of course, you can check various questions on this site with [generating-functions] tag.