What kind of relation is this?

The characteristic equation of the linear recurrence relation $a_n = a_{n-1}+6a_{n-2}$ is as follows:

$\begin{aligned} r^2+r-6 & = 0 \\ (r-2)(r+3) & = 0 \\ \implies r & = 2, - 3 \end{aligned}$

Let $b_n = a_{n+1}$ , $\implies a_1 = b_0 = 2$ and $a_2 = b_1 = 1$ and:

$\begin{aligned} b_n & = c_1(2^n) + c_2(-3)^n \\ b_0 & = c_1 + c_2 = 2 \\ b_1 & = 2c_1 -3 c_2 = 1 \\ \implies c_1 & = \frac 75 \\ \implies c_2 & = \frac 35 \\ \implies b_n & = \frac {7(2^n) + (-1)^n3^{n+1}}5 \end{aligned}$

Therefore, we have:

$\begin{aligned} a_{100}+3a_{99} & = b_{99}+3b_{98} \\ & = \frac {7(2^{99})-3^{100} + 21(2^{98}) + 3^{100}}5 \\ & = \frac {14(2^{98})+21(2^{98})}5 \\ & = \boxed{7 \times 2^{98}} \end{aligned}$

Let $x_n \equiv a_n + 3\,a_{n-1}$ . We are seeking $x_{100}$ . Note that since $a_1 = 2$ and $a_2=1$ , then $x_2 = a_2 + 3\, a_1 = 1 + 3(2) = 7$ . Using the recursion relation $a_n = -a_{n-1} + 6 \, a_{n-2}$ , we have:

$\qquad x_n = a_n + 3\, a_{n-1} \;=\; (-a_{n-1} + 6 \, a_{n-2}) + 3\; a_{n-1} \;=\; 2\,a_{n-1} + 6 \, a_{n-2} \;=\; 2 (a_{n-1} + 3\, a_{n-2}) \; =\; 2 \,x_{n-1}$ .

Iterative substitution gives: $x_n = 2 \,x_{n-1} = 2^2 \, x_{n-2} = \cdots = 2^k \, x_{n-k}$ . After $k=n-2$ iterations, $x_n = 2^{n-2} \, x_2 = 2^{n-2} \cdot 7$ .

Therefore, when $n=100$ , $\boxed{x_{100} = 7 \times 2^{98}}$ .