Technique
The basic technique is to multiply the equation with \(z^{N}\), sum over all \(N\), recast in terms of the generating function (or derivative, etc). Then solve for the generating function, and expand to get the coefficient of \(z^{N}\). That will be your solution.
One very important caveat is that one must account for the initial conditions! You cannot solve for it in the end - they are part of your equation from the start!
Example
\begin{equation*}
a_{n}=5a_{n-1}-8a_{n-2}+4a_{n-3},a_{0}=0,a_{1}=1,a_{2}=4
\end{equation*}
becomes:
\begin{equation*}
a_{n}=5a_{n-1}-8a_{n-2}+4a_{n-3}+\delta_{n,1}-\delta_{n,2}
\end{equation*}
How did I get these? Assume that if the index is negative, the value is 0. Then plug in \(n=1\) and figure out what term to add to make the equation valid for \(a_{1}\), and so on.
Now multiply by \(z^{n}\) and sum:
\begin{equation*}
A(z)=5zA(z)-8z^{2}A(z)+4z^{3}A(z)+z-z^{2}
\end{equation*}
Solve for \(A(z)\), decompose into partial fractions, and get the solution.
Notes
- When you have constant coefficient linear equation, if your root is complex, there will be some kind of periodicity!
- If a root is -1, you’ll get some periodicity.