Recursive function guess

Question

$$ $$ I am having trouble with getting the right guess because the right side of the function is a constant. How do I get the right guess? I need to find the general solution

Answer 1

It is worth noting that the method of generating functions does not require a guess. Let $f(z) = \sum_{n=0}^\infty y_n z^n$ be the ordinary generating function. Then the recurrence implies that $$\sum_{n=0}^\infty (y_{n+2} - 3 y_{n+1} + 2y_{n}) z^{n+2} = \sum_{n=0}^\infty 5 z^{n+2}.$$ So $$(f(z)-y_0z^0-y_1z^1)-3z(f(z)-y_0z^0) + 2z^2 f(z) = \frac{5 z^2}{1-z}.$$ Solving for $f(z)$ yields \begin{align} f(z) &= \frac{\frac{5 z^2}{1-z}+y_0+y_1z-3 y_0 z}{1-3z+2z^2}\\ &=\frac{5 z^2+(1-z)(y_0+y_1z-3 y_0 z)}{(1-z)^2(1-2z)}\\ &=\frac{A}{(1-z)^2}+\frac{B}{1-z}+\frac{C}{1-2z} \\ &=A\sum_{n=0}^\infty \binom{n+1}{1}z^n + B\sum_{n=0}^\infty z^n+C\sum_{n=0}^\infty (2z)^n, \end{align} which immediately yields general solution $$y_n = A(n+1) + B+C\cdot2^n.$$ If you prefer, replace the $A+B$ with a constant $D$: $$y_n = An+D+C\cdot2^n.$$

---

Solving the linear system \begin{align} A\cdot 0+D+C\cdot2^0 &= y_0 \\ A\cdot 1+D+C\cdot2^1 &= y_1 \\ A\cdot 2+D+C\cdot2^2 &= y_2 = 5+3y_1-2y_0 \end{align} for $(A,D,C)$ in terms of $y_0$ and $y_1$ yields \begin{align} A &= -5 \\ D &= 2 y_0 - y_1 - 5 \\ C &= -y_0 + y_1 + 5 \end{align}