Example: finding a linear recurrence from an explicit formula

Let $a_n=(n+2^n)F_n$, where $\{F_n\}$ is the Fibonacci sequence. Then by the explicit formula for $F_n$,

$$a_n = (n+2^n) \left( \frac{\alpha^n-\beta^n}{\alpha-\beta} \right)$$

$$= \left[ \left( \frac{1}{\alpha-\beta} \right) n \right] \alpha^n... ...\beta} \right) (2\alpha)^n + \left( \frac{-1}{\alpha-\beta} \right) (2\beta)^n.$$

By Theorem 1, $\{a_n\}$ satisfies a linear recurrence with characteristic polynomial

$$(x-\alpha)^2(x-\beta)^2(x-2\alpha)(x-2\beta) = (x^2-x-1)^2 \left[ x^2-2(\alpha+\beta)+4\alpha\beta \right]$$

$$= (x^2-x-1)^2(x^2-2x-4)$$

$$= x^6-4x^5-x^4+12x^3+x^2-10x+4,$$

where we have used the identity $x^2-(\alpha+\beta)x+\alpha\beta=x^2-x-1$ to compute $\alpha+\beta$ and $\alpha\beta$. In other words,

$$a_{n+6} - 4 a_{n+5} - a_{n+4} + 12 a_{n+3} + a_{n+2} - 10 a_{n+1} + 4 a_n = 0$$

for all $n$. In fact, we have found the minimal characteristic polynomial, since if the actual minimal characteristic polynomial were a proper divisor of $(x^2-x-1)^2(x^2-2x-4)$, then according to Theorem 1, the explicit formula for $a_n$ would have had a different, simpler form.