Find a functional equation for the generating function whose coefficients satisfy the relation:

$\qquad{}$ $a_n = 3a_{n-1} -2a_{n-2}+2, a_0=a_1=1$

When I solve this, I get the function $g(x)-1-x=3xg(x)-2x^2g(x)$

However, the correct answer is supposed to be $g(x)-1-x = 3xg(x)-3-2x^2g(x)+\frac{2x^2}{1-x}$

Where does the $-3$ and the $\frac{2x^2}{1-x}$ come from?


Mostly you forgot to take into account the $+2$ term in the recurrence, though there is one other problem. For $n\ge2$ you have


so when you sum over $n\ge 2$ you get

$$\sum_{n\ge 2}a_nx^n=3\sum_{n\ge 2}a_{n-1}x^n-2\sum_{n\ge 2}a_{n-2}x^n+2\sum_{n\ge 2}x^n\;.$$

The lefthand side is $g(x)-1-x$, so

$$\begin{align*} g(x)-1-x&=3x\sum_{n\ge 2}a_{n-1}x^{n-1}-2x^2\sum_{n\ge 2}a_{n-2}x^{n-2}+\frac{2x^2}{1-x}\\ &=3x\sum_{n\ge 1}a_nx^n-2x^2\sum_{n\ge 0}a_nx^n+\frac{2x^2}{1-x}\\ &=3x\big(g(x)-1\big)-2x^2g(x)+\frac{2x^2}{1-x}\\ &=3xg(x)-3x-2x^2g(x)+\frac{2x^2}{1-x}\;. \end{align*}$$

Note that it’s $-3x$, not $-3$; either you or your answer key seems to have a typo.

  • 1
    $\begingroup$ Yeah, -3 didn't look right, since the constant term of the left side is zero, and the there is no constant terms in any of the other parts of the answer other than the -3.... $\endgroup$ – Thomas Andrews Apr 21 '16 at 1:27
  • 1
    $\begingroup$ Indeed, you can write it as $g(x)-x-1 = 3xg(x)-2x^2g(x) + 2\frac{x^2}{1-x}-(ax+b)$ and use that the left side has the first two terms $0+0x+\dots$ to solve for $a,b$. $\endgroup$ – Thomas Andrews Apr 21 '16 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.