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

1k Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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.