Solving a nonhomogeneous recurrence relation

Question

How does one solve a recurrence relation of the kind $u_{k+1} = u_k + u_{k-1} + a \cdot \cos(\omega k)$ for arbitrary $a > 0$ and $\omega > 0$?

Answer 1

Let us take the Z transform from both sides. One can conveniently use the properties of the Z-transform listed in Wikipedia, as well as table of common Z-transforms. We get:

$$z \psi= \psi +z^{-1} \psi +a \frac{1-z^{-1} \cos(\omega)}{1- 2 z^{-1} cos(\omega) +z^{-2}} $$ This can be recast as $$ \psi= a \frac{1-z^{-1} \cos(\omega)}{\bigg[1- 2 z^{-1} cos(\omega) +z^{-2}\bigg] \big(z-1-z^{-1} \big) } $$ You can easily expand this in powers of $z^{-1}$. We have: $$ \psi= \frac{a}{z}+a \frac{1+\cos(\omega)}{z^2} + a \frac{1+\cos(\omega)+2 \cos^2(\omega)}{z^3} + a \frac{2-\cos(\omega)+2 \cos^2(\omega)+4 \cos^2(\omega)}{z^4}+\ldots $$ Using straightforward trigonometric identities, we observe that the coefficient of $z^{-k}$, which is $u_k$, is given by $$u_k =a \sum_{\ell=0}^{k-1} F_{k-\ell} \cos\big(\omega \ell \big), $$ where $F_j$ denotes the j-th Fibonacci number: $$ F_1=1, F_2=1, F_3= 2, F_4= 3, F_5 = 5, F_6= 8 \ldots $$

Answer 2

I would treat is as the real part of $u_{k+1} = u_k + u_{k-1} + a e^{i\omega k} = u_k + u_{k-1} + a c^k $ (where $c = e^{i \omega} $), solve this, and then take the real part of the solution.