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?

Solutions Collecting From Web of "How to get the characteristic equation from a recurrence relation of this form?"

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.

The characteristic equation gets you solutions of a homogeneous equation,
in this case $f(n) = f(n+1)$ (but that’s too trivial, those solutions are constant). You then have to add particular solutions of the non-homogeneous equation. In this case look for a polynomial of degree $2$ solving $f(n) = f(n+1) + 3 + 2n$ and $2^n c$ solving $f(n) = f(n+1) + 2^n$.