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.
 A: Let $\lambda_1,\ldots,\lambda_k$ and $\alpha_1,\ldots,\alpha_k$ be real numbers and suppose we define a sequence by the recurrence relation $$a(n) = \sum_{i=1}^{k} \lambda_i a(n-i) \tag{1}$$
With initial conditions $$a(n) = \alpha_n \text{ for }i=1,\ldots,k \tag{2}$$
If $r = r(n)$ and $g=g(n)$ are sequences that satisfies (1), then $r+a\ g = r(n) + a\ g(n)$ also satisfies (1): 
$$r(n) + a \ g(n) = \sum_{i=1}^{k} \lambda_i r(n-i) + a \ \sum_{i=1}^{k} \lambda_i g(n-i) = \sum_{i=1}^{k} \lambda_i (r(n-i)+a\ g(n-i))$$
So the space of all functions from $\mathbb{N}$ to $\mathbb{C}$ (I'll explain using complex later) that satisfies (1) has the property that every linear combination is also a solution. Since we can define a neutral element and opposite element for every sequence that satisfies (1), we say the set of all the functions satisfying (1) has the structure of a vector space. 
The main idea of solving a linear recurrence is finding a suitable basis for this space, that is, a minimal set $B \subset V$ such that every element of $V$ is a linear combination of elements of $B$. The dimension of this space (i.e. the size of the basis) can be shown to be $k$, but I can't think of any elementary method.
So the problem reduces to finding a suitable basis!
Suppose that for some $u \in \mathbb{C}$ we have $b(n)= u^n \in V$.
So, $b$ satisfies (1): $$u^n =  \sum_{i=1}^{k} \lambda_i u^{n-i}$$ And let assume that $u \neq 0$, then we have $$u^k = \sum_{i=1}^k \lambda_i u^{k-i}$$ 
So, if we solve the polynomial in u:
$$u^k - \lambda_1 u^{k-1} + \cdots - \lambda_{k-1}u - \lambda_{k}=0 \tag{3}$$
By the fundamental theorem of algebra (now, we need $\mathbb{C}$ here!), we now that (3) has $k$ or less roots.
We call (3) the characteristic equation of recurrence (1)
Assume that (3) has $k$ different roots $u_1, \ldots, u_k$, then each $b_i = (u_i)^n$ is a solution.
If (3) has less than $k$ solutions, let $u$ be a solution of multiplicity $m$, then $b(n) = u^n$ is a solution but also $c_j = n^j u^j$ for $j=1,\ldots,m-1$, so this solve the problem completely, because we alredy found a basis having $k$ elements (check it!), and using (2), we can find a unique solution to our recurrence relation
A: Yes, it's homogeneous because it has no constant terms.
Yes, it can be solved. The closed form is$$a_n = A\alpha_1^n + B\alpha_2^n$$where the $\alpha_i$ are the roots of the characteristic equation $u^2 - 6u + 1 = 0$ and the $A$ and $B$ are constants determined by the initial conditions $a_1$ and $a_2$.
For more detail, see the wikipedia page referenced above.
A: The pairs $(a_n, b_n)$ such as
$$ (1,4),  $$
$$ (6,23),  $$
$$ (35,134),  $$
$$ (204,781),  $$
with $$ a_{n+2} = 6 a_{n+1} - a_n  $$ and
$$ b_{n+2} = 6 b_{n+1} - b_n  $$
satisfy
$$ \color{blue}{7 a^2 + 2 a b - b^2 = -1}.  $$
Just saying.
EDIT, Saturday: I had picked the cleanest quadratic form version of this, from comment by the OP, it was actually this:
$$ \color{magenta}{8 a^2 - (2b+1)^2 = -1}.  $$
$$ (0,0),  $$
$$ (1,1),  $$
$$ (6,8),  $$
$$ (35,49),  $$
$$ (204,288),  $$
$$ (1189,1681),  $$
with $$ a_{n+2} = 6 a_{n+1} - a_n  $$ and
 $$ b_{n+2} = 6 b_{n+1} - b_n + 2.  $$
Notice how the $b_n$ recursion includes a constant $2.$ 
To get a recursion of order 1, we need to take the pair together:
$$ \color{red}{(a_{n+1}, b_{n+1}) = (3 a_n + 2 b_n + 1, 4 a_n + 3 b_n + 1)} $$
A: As user164587 answered, the closed form is $$a_n = A\alpha_1^n + B\alpha_2^n$$ where $\alpha_1$ and $\alpha_2$ are the roots of the characteristic equation $u^2 - 6u + 1 = 0$ that is to say $\alpha_1=3-2 \sqrt{2}$, $\alpha_2=3-2 \sqrt{2}$. 
Solving for $A$ and $B$, you would find that $$A=-\frac{{a_2}-{a_1} {\alpha_2}}{{\alpha_1} ({\alpha_2}-{\alpha_1})}$$ $$B=-\frac{{-a_2}+{a_1} {\alpha_1}}{{\alpha_2} ({\alpha_2}-{\alpha_1})}$$
Using the values of $a_1,a_2,\alpha_1,\alpha_2$, you then arrive to $$a_n= \frac{\left(3+2 \sqrt{2}\right)^n-\left(3-2 \sqrt{2}\right)^n}{4 \sqrt{2}}$$ which is a simple expression. 
A: 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$$
