Amateur Math and a Linear Recurrence Relation I haven't received a formal education on this topic but a little googling told me this is what I am trying to find. I would like to put
$$ a_n = 6 a_{n-1} - a_{n-2} $$
$$ a_1 =1, a_2 = 6 $$
into its explicit form. So far I have only confused myself with billions of 6's.
I would like someone to respond with the following:


*

*Is this relation homogenous? (not sure if subtraction counts)

*Is there a basic way I can solve this type of recurrence? (I don't need the long answer, just enough to satisfy curiosity)
I am not necessarily looking for only a solution to this problem but one would be appreciated nonetheless. Still, I am more interested in the background and would better appreciate that than simply some formula.

Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence without subtractions in indices:
$$
a_{n + 2}
  = 6 a_{n + 1} - a_n
$$
Run the recurrence "backwards" to get $a_0 = 0$ for simplicity.
Multiply the recurrence by $z^n$, sum over $n \ge 0$, and recogize some sums:
$$
\frac{A(z) - a_0 - a_1 z}{z^2}
  = 6 \frac{A(z) - a_0}{z} - A(z)
$$
With the initial values, we can solve for $A(z)$:
$$
A(z)
  = \frac{z}{1 - 6 z + z^2}
  = \frac{1}{2^{5/2}} \cdot \frac{1}{1 - (3 + 2^{3/2}) z}
      - \frac{1}{2^{5/2}} \cdot \frac{1}{1 - (3 - 2^{3/2}) z}
$$
Quite ugly, but just two geometric series:
$$
a_n
  = \frac{1}{2^{5/2}} \cdot \left(3 + 2^{3/2}\right)^n
      - \frac{1}{2^{5/2}} \cdot \left(3 - 2^{3/2}\right)^n
$$
Note that:
$$
3 + 2^{3/2} \approx 5.8284 \\
3 - 2^{3/2} \approx 0.1716
$$
so that:
$$
a_n \sim \frac{1}{2^{5/2}} \cdot \left(3 + 2^{3/2}\right)^n
$$
The notation $f(n) \sim g(n)$ means
$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$$
