how can I use generating functions to solve the recurrence relation $$a_n = 4a_{n-1} -4a_{n-2}$$

$$a_1 = 1, a_2=3$$

some terms: 1,3,8,20,48

$$a_n -4a_{n-1} +4a_{n+2} =0$$

$$f(x)= 1+3x+ 8x^2 +20x^3+\dots$$ $$-4xf(x)= 4x+12x^2 +32x^3$$ $$4x^2f(x)= 4x^2 +12x^3 +32x^4$$


so I get $f(x)=\frac {1-x}{1-4x+4x^2}$ but I think it should be $f(x)= \frac {x-x^2}{1-2x^2}$ dunno where it went wrong.

and then I'm wondering how can I find $a_n$ now that I have the generating function?


1 Answer 1


Start by setting up your generating function: $$ F(x):=\sum_{n=1}^{\infty}a_nx^n. $$ Now, using the recurrence relation that $a_n=4a_{n-1}-4a_{n-2}$, you can rewrite this as $$ \begin{align*} F(x)&=\sum_{n=1}^{\infty}a_nx^n\\ &=a_1x+a_2x^2+\sum_{n=3}^{\infty}a_nx^n\\ &=a_1x+a_2x^2+\sum_{n=3}^{\infty}(4a_{n-1}-4a_{n-2})x^n\\ &=a_1x+a_2x^2+4x\sum_{n=3}^{\infty}a_{n-1}x^{n-1}-4x^2\sum_{n=3}^{\infty}a_{n-2}x^{n-2}\\ &=a_1x+a_2x^2+4x\sum_{n=2}^{\infty}a_nx^n-4x^2\sum_{n=1}^{\infty}a_nx^n. \end{align*} $$ These last two sums are closely related to your original generating function $F(x)$. See if you can rewrite this formula by leveraging that fact, to get a functional relation satisfied by $F(x)$; from there, solving for $F(x)$ will give you an explicit generating function for $(a_n)$, and from there an explicit expression for $(a_n)$ itself.

  • $\begingroup$ how can I find F(x) from that? $\endgroup$
    – eyy321
    Nov 24, 2015 at 19:28
  • $\begingroup$ You will end up with an equation that looks like $F(x)=\text{(something in terms of $F(x)$)}$. Then, treating $F(x)$ as an unknown quantity, you can solve for $F(x)$ explicitly. $\endgroup$ Nov 24, 2015 at 19:59
  • $\begingroup$ so what did u get F(x) to be and how?? $\endgroup$
    – eyy321
    Nov 24, 2015 at 20:51
  • 1
    $\begingroup$ I'm not going to give you the answer. You have all the parts you need to get that. Notice that one of the two sums above is exactly $F(x)$, and the other one would be if it wasn't missing one term. $\endgroup$ Nov 24, 2015 at 22:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .