I am learning about Generating Functions to solve non-homogenous linear recurrences, and I can't seem to get the right solution, no matter what I do.
Also, the example I have to work off of in the text book has an error...and for the life of me, (well, for a few hours now anyway) I can't figure it out/get a working solution for $r_n$ for either the example recursion, or any of the practice recursions at the end of the chapter...
Here is the setup in the textbook:
And it continues with the problem on the next page:
And, finally, the solution:
The correct sequence is:
$$ r_n = 2^n + r_{n-1} + 2r_{n-2}, \text{ such that }r_0 = 2, r_1 = 1\text{ yielding: }\\ \{2,1,9,...\} $$
While the solution in the book yields (from the wolfram alpha input posted below):
$$ \{3,4,14,30,...\} $$
Wolfram Alpha input:
(17/9)2^n + (2/3)n*2^n + (10/9)(-1)^n, for n = {0,1,2,3}
I thought I spotted a typo where the author said $\frac{1}{(1-2x)} = \sum_{n=2}^{\infty}2^n x^n \text{ instead of } \frac{1}{(1-2x)} - (1 + 2x) = \sum_{n=2}^{\infty}2^n x^n$, but that didn't pan out either.
I'm not really sure where else the error could be...
Also, wolfram alpha gives a solution for the recursion,
in: r_n - r_{n-1} - 2*r_{n-2} = 2^n such that r_0 = 2 and r_1 = 1 out: $ r_n = c_1(-2)^{n-1} + \frac{1}{9}(2^n(4(-1)^n - 9) + 3n + 5)$
in: -4(-2)^(n-1) + (1/9)(2^n(4(-1)^n - 9) + 3n +5) for n = {0,1,2,3}
Where I use the only constant, $c_1$ to set $r_0$ to 2...
out: {2,-6,7,-26,...}
I think that if I have at least one working example, I will be set...
Also, solved it using the advancement operator, and got:
$ \frac{n2^n}{6} + \frac{8}{9}2^n + \frac{10}{9}(-1)^n$
which yields: $\{2,1,6,10\}$, so at least that is close (I probably made a mistake somewhere)...but I think I need at least one working solution to this thing to get the hang of this...
You did catch an error on the righthand side, and that error is the source of the problems:
$$\sum_{n\ge 2}2^nx^n=\frac{4x^2}{1-2x}\;.$$
This means that
$$\begin{align*} R(x)&=\frac{4x^2}{(1-2x)(1-x-2x^2)}+\frac{2-x}{1-x-2x^2}\\ &=\frac{6x^2-5x+2}{(1-2x)^2(1+x)}\\ &=\frac19\left(\frac{-1}{1-2x}+\frac{6}{(1-2x)^2}+\frac{13}{1+x}\right)\\ &=\frac19\sum_{n\ge 0}\big(-2^n+6(n+1)2^n+13(-1)^n\big)x^n\\ &=\frac19\sum_{n\ge 0}\big((6n+5)2^n+13(-1)^n\big)x^n\;, \end{align*}$$
so that
$$r_n=\frac{(6n+5)2^n+13(-1)^n}9\;.$$
This does yield the correct values of $2,1,9$, and $19$ for $n=0,1,2$, and $3$, respectively.