# Solving recursion with generating function

I am trying to solve a recursion with generating function, but somehow I ended up with mess..... $$y_n=y_{n-1}-2y_{n-2}+4^{n-2}, y_0=2,y_1=1$$ \begin{eqnarray*} g(x)&=&y_0+y_1x+\sum_2^{\infty}(y_{n-1}-2y_{n-2}+4^{n-2})x^n\\ &=&2+x+\sum^{\infty}_2y_{n-1}x^n-2\sum_2^{\infty}y_{n-2}x^n+\sum_2^{\infty}4^{n-2}x^n\\ &=&2+x+x\sum_1^{\infty}y_{n-1}x^{n-1}-2x^2\sum_0^{\infty}y_{n-2}x^{n-2}+\frac{1}{4^2}\sum^{\infty}_{2}(4x)^{n}\\ &=&2+x+x(g(x)-1)-2x^2g(x)+\frac{1}{4^2}\left(\frac{1}{1-4x}-1-4x\right)\\ g(x)(1-x+2x^2)&=&2+\frac{1}{4^2}\frac{1}{1-4x}-\frac{1}{4^2}-\frac{x}{4}\\ g(x)&=& \frac{x^2-8x+2}{(1-4x)(1-x+2x^2)} \end{eqnarray*} How do I go from here to get $y_n$ as a complete solution, and also I noticed that $(1-x+2x^2)$ has imaginary roots, what does it mean? no solution?

-
The eigenvalues are $\sqrt{2}e^{\pm i \arctan \sqrt{7}}$. The difference equation must have a solution, as it is defined explicitly. Explicitly computing the transition matrix is a mess. – copper.hat Mar 20 '13 at 2:26

## 3 Answers

I get a slightly different result from you. Let

$$y(x) = \sum_{n=0}^{\infty} y_n x^n$$

Then, summing the recurrence relation from $n=2$ on, I get

$$y(x) - y_0 - y_1 x - x [y(x)-y_0] + 2 x^2 y(x) = \frac{x^2}{1-4 x}$$

Simplifying, using the initial conditions $y_0=2$ and $y_1=1$:

$$(2 x^2-x+1)y(x) = \frac{x^2}{1-4 x} + 2-x = \frac{5 x^2-9 x+2}{1-4 x}$$

Therefore the generating function is

$$y(x) = \frac{5 x^2-9 x+2}{(1-4 x)(2 x^2-x+1)}$$

Your concern about whether the denominator has complex roots is unfounded. The roots of the quadratic in the denominator are based on the characteristic equation for the recurrence that leads to the homogeneous solution. When the roots of this equation are complex, then there is both exponential growth and oscillatory behavior; this is quite normal.

-
I get the same generating function by a slightly different computational technique. – Brian M. Scott Mar 20 '13 at 4:21
@BrianM.Scott Would you be able to post your calculations? From the 3rd to the 4th line in Ron's answer and user's it looks like the index shifts from 2 to 0 without reason. This would make the sum begin at $y_{-2}$ – 114 Apr 22 '13 at 13:19
@Stopwatch: By convention I take $y_n=0$ for all $n<0$. The recurrence is therefore $$y_n=y_{n-1}-2y_{n-2}+4^{n-2}+\frac{31}{16}[n=0]-\frac54[n=1]\;,$$ where I’m using Iverson brackets to account for the initial values. (E.g., without them the recurrence would make $y_0=4^{-2}$, on the assumption stated above, so I need to add another $\frac{31}{16}$.) Then multiply through by $x^n$ and sum over $n\ge 0$. The first term on the righthand side does yield a summation whose $n=0$ term has a coefficient $y_{-1}$, but that’s $0$ and causes no trouble. – Brian M. Scott Apr 23 '13 at 10:25

Use the technique in Wilf's "generatingfunctionology" Define the generating function $A(z) = \sum_{n \ge 0} y_n z^n$, and write: $$y_{n + 2} = y_{n + 1} - 2 y_n + 4^n \quad y_0 = 2, y_1 = 1$$ Using properties of generating functions: $$\frac{A(z) - y_0 - y_1 z}{z^2} = \frac{A(z) - y_0}{z} - 2 A(z) + \frac{1}{1 - 4 z}$$ Solving for $A(z)$, reducing to partial fractions: $$A(z) = \frac{17z - 27}{14 (1 - z + 2 z^2)} + \frac{1}{14} \frac{1}{1 - 4 z}$$ The first term's denominator splits into: $$\left( 1 - \frac{1 + i \sqrt{7}}{2} z \right) \left(1 - \frac{1 - i \sqrt{7}}{2} z \right)$$ This gets quite ugly, and sadly the magnitude of those is also 4. This gives a solution that fluctuates wildly. The full solution is of the form: $$y_n = \alpha \left(\frac{1 + i \sqrt{7}}{2}\right)^n + \overline{\alpha} \left(\frac{1 - i \sqrt{7}}{2}\right)^n + \frac{4^n}{14}$$ for some complex constant $\alpha$.

-

Once you have $g(x)$ as a rational function (quotient of two polynomials), you can use the partial fractions technique you may have learned if you studied Calculus to write that rational function as (in your case) a sum of terms each of the form $${A\over1-\beta x}$$ Then you can expand each of those terms as a geometric series, $${A\over1-\beta x}=\sum_0^{\infty}A\beta^nx^n$$ and you will wind up with a generating function whose coefficients are of the form $$A_1\beta_1^n+A_2\beta_2^n+\cdots+A_r\beta_r^n$$ and there is your solution.

-