<s>[INST] How to get the characteristic equation from a recurrence relation of this form? I've been getting the characteristic equation from relations of the form
$$U_n=3U_{n-1}-U_{n-3}$$
Thanks to this question I made before: How to get the characteristic equation?

Now, I recently have been asked to get such equation from this:
$$f(n) = \begin{cases}5 & \text{ if  n = 0} \\ f(n-1) + 3 + 2n + 2^n \end{cases}$$
I tried to apply the same idea. I took:
$$F_n=F_{n-1} + 3 + 2n + 2^n$$
Changed the subscripts to exponents...
$$F^n=F^{n-1} + 3 + 2n + 2^n$$
Replaced $F$ by the desired variable...
$$x^n=x^{n-1} + 3 + 2n + 2^n$$
Divided by the smallest exponent (I guess it is $n-1$):
$$x=1+ 3^{-x+1} + 2n^{-x+1} + 2^{n-x+1}$$
And this doesn't look right. As you can see, the terms $3$, $2n$ and $2^n$ messed up the whole thing.
What did I do wrong, and how can I get the characteristic equation from this?
 [/INST] Use the machinery of generating functions. Define $F(z) = \sum_{n \ge 0} f(n) z^n$, and write your recurrence as:
$$
f(n + 1) = f(n) + 5 + 2 n + 2^{n + 1}
$$
Multiply the recurrence by $z^n$, sum over $n \ge 0$ and recognize:
\begin{align}
\sum_{n \ge 0} f(n + 1) z^n &= \frac{F(z) - f(0)}{z} \\
\sum_{n \ge 0} z^n          &= \frac{1}{1 - z} \\
\sum_{n \ge 0} n z^n        
  &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\
  &= \frac{z}{(1 - z)^2} \\
\sum_{n \ge 0} 2^n z^n
  &= \frac{1}{1 - 2 z}
\end{align}
Pulling all together:
$$
\frac{F(z) - 5}{z} 
   = F(z) + \frac{5}{1 - z} + \frac{2 z}{(1 - z)^2} + \frac{2}{1 - 2 z}
$$
Solving for $F(z)$, as partial fractions:
$$
F(z) = \frac{5 - 13 z + 8 z^2 - 2 z^3}{1 - 5 z + 9 z^2 - 7 z^3 + 2 z^4}
     = \frac{2}{1 - 2 z} + \frac{1}{(1 - z)^2} + \frac{2}{(1 - z)^3}
$$
Using the (generalized) binomial theorem:
\begin{align}
f(n) &= 2 \cdot 2^n + \binom{-2}{n} (-1)^n + 2 \cdot \binom{-3}{n} (-1)^n \\
     &= 2^{n + 2} + \binom{n + 2 - 1}{1} + 2 \cdot \binom{n + 3 - 1}{2} \\
     &= 2^{n + 1} + n + 1 + \frac{(n + 2) (n + 1)}{2} \\
     &= 2^{n + 1} + \frac{n^2 + 5 n + 4}{2}
\end{align}
Maxima's help with the algebra is gratefully acknowledged.
</s>