Amateur Math and a Linear Recurrence Relation

Question

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:

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

2. 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.

Answer 1

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

Answer 2

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.

Answer 3

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)} $$

Answer 4

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.

Answer 5

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$$