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

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

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

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.

• 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.... – Thomas Andrews Apr 21 '16 at 1:27
• 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$. – Thomas Andrews Apr 21 '16 at 1:29