Using generating functions to solve recurrences

Consider the recurrence equation \(r_{n}+r_{n-1}-6r_{n-2} = 0\) for the sequence \(\{r_n\colon n\geq 0\}\) with \(r_0=1\) and \(r_1=3\). This sequence has generating function \[\begin{aligned}\end{aligned}\] Now consider for a moment what the function \(xf(x)\) looks like. It has \(r_{n-1}\) as the coefficient on \(x_n\). Similarly, in the function \(-6x^2 f(x)\), the coefficient on \(x^n\) is \(-6r_{n-2}\).

What is our point in all of this? Well, if we add them all up, notice what happens. The coefficient on \(x_n\) becomes \(r_n+r_{n-1}-6r_{n-2}\), which is \(0\) because of the recurrence equation! Now let's see how this all lines up: \[\begin{aligned}f(x) \amp = r_0 + r_1 x + r_2x^2 + r_3 x^3 + \cdots + r_nx^n + \cdots \\ xf(x) \amp = 0 + r_0 x + r_1x^2 + r_2 x^3 + \cdots r_{n-1}x^n + \cdots \\ -6x^2f(x) \amp = 0 + 0 -6r_0x^2 - 6r_1 x^3 + \cdots - 6r_{n-2}x^n + \cdots\end{aligned}\] When we add the left-hand side, we get \(f(x)(1+x-6x^2)\). On the right-hand side, the coefficient on \(x^n\) for \(n\geq 2\) is \(0\) because of the recurrence equation. However, we are left with \(r_0 + (r_0+r_1)x = 1 + 4x\), using the initial conditions. Thus, we have the equation \[\begin{aligned}\end{aligned}\] or \(f(x) = (1+4x)/(1+x-6x^2)\). This is a generating function that we can attack using partial fractions in SageMath:

This shows us that \[\begin{aligned}\end{aligned}\]. From here, we read off \(r_n\) as the coefficient on \(x^n\) and have \(r_n = (6/5) 2^n -(1/5)(-3)^n\).