explicit formula for $a_n$ and $b_n$

Question

Let $a_n$ and $b_n$ be natural sequence such that $$a_n+b_n\sqrt3=(1+\sqrt3)^n$$ How can I find explicit formula for $a_n$ and $b_n$

Answer 1

If you write the equality for $n+1$, one gets $a_{n+1}=a_n+3b_n$ and $b_{n+1}=a_n+n_n$. Defining the pair $a_n,b_n$ as a column vector $c_n$, one has $$c_{n+1}= \left( \begin{array}{cc} 1 & 3 \\ 1 & 1 \\ \end{array} \right)c_n$$, with $c_0=(1,0)^T$ (transpose). With $M\equiv\left( \begin{array}{cc} 1 & 3 \\ 1 & 1 \\ \end{array} \right) $, the solution is $$ c_n=M^n \left( \begin{array}{c} 1 \\ 0 \\ \end{array} \right).$$

You need to find $M^n$ (using the usual eigenvalue decomposition).

Answer 2

This question and answer show that $a_n$ and $b_n$ satisfy the recurrences

$$\begin{align*} &a_n=a_{n-1}+3b_{n-1}\\ &b_n=a_{n-1}+b_{n-1}\;. \end{align*}\tag{1}$$

If we add $2a_{n-1}$ to both sides of the first recurrence, we get

$$a_n+2a_{n-1}=3a_{n-1}+3b_{n-1}=3(a_{n-1}+b_{n-1})=3b_n\;,$$

and we can shift the indices down $1$ to get

$$a_{n-1}+2a_{n-2}=3a_{n-2}+3b_{n-2}=3b_{n-1}\;.$$

Substituting this into the first recurrence yields

$$a_n=a_{n-1}+3b_{n-1}=a_{n-1}+a_{n-1}+2a_{n-2}=2a_{n-1}+2a_{n-2}\;,\tag{2}$$

with initial values $a_0=a_1=1$; this can be solved by any standard technique.

We also see that

$$a_n=a_{n-1}+3b_{n-1}=(a_{n-1}+b_{n-1})+2b_{n-1}=b_n+2b_{n-1}\;,$$

and we can add $b_n$ to both sides to get

$$b_{n+1}=a_n+b_n=2b_n+2b_{n-1}$$

or, after shifting the indices,

$$b_n=2b_{n-1}+2b_{n-2}\;.\tag{3}$$

Thus, both sequences satisfy the same recurrence.

The manipulations needed to turn the original recurrences into separate ones for the $a_n$ and the $b_n$ are probably not obvious. They can be found in many ways. For instance, they can be found by tinkering, by computing $a_n$ and $b_n$ for $n=0,1,2,3,4,5$, say, spotting the pattern and then proving it by induction, or by computing those same values and looking up the sequences in The On-Line Encyclopedia of Integer Sequence. That last approach yields only one possible match for each, OEIS A026150 for the $a_n$ and OEIS A002605 for the $b_n$. Each of the OEIS sequences satisfies the recurrence $(2)$, so you can either try to manipulate $(1)$ to get $(2)$ and $(3)$, or you can try to use $(1)$ to prove by induction that the $a_n$ and $b_n$ satisfy $(2)$ and $(3)$, respectively.

There are of course other ways to solve $(1)$, e.g., by noting that it’s equivalent to the matrix recurrence

$$\begin{bmatrix}a_n\\b_n\end{bmatrix}=\begin{bmatrix}1&3\\1&1\end{bmatrix}\begin{bmatrix}a_{n-1}\\b_{n-1}\end{bmatrix}\;.$$

Setting $A=\begin{bmatrix}1&3\\1&1\end{bmatrix}$, we can readily infer that

$$\begin{bmatrix}a_n\\b_n\end{bmatrix}=A^n\begin{bmatrix}a_0\\b_0\end{bmatrix}=A^n\begin{bmatrix}1\\0\end{bmatrix}$$

and use linear algebra techniques to get an explicit form for $A^n$.

Answer 3

There is a solution using linear algebra. From

$$a_n+b_n\sqrt{3}=(1+\sqrt{3})^n \ \ \ (1)$$

we deduce:

$$\begin{cases}a_n=a_{n-1}+3b_{n-1}\\ b_n=a_{n-1}+b_{n-1}\end{cases} \ \ \ (2)$$

which can be expressed under the following recurrence relationship:

$$\binom{a_n}{b_n}=M \binom{a_{n-1}}{b_{n-1}} \ \ \text{with} \ \ \binom{a_{1}}{b_{1}}=\binom{1}{1} \ \ \ (3)$$

with

$$M:=\begin{pmatrix}1&3\\1&1\end{pmatrix}$$

In other terms:

$$\binom{a_n}{b_n}=M^n\binom{a_1}{b_1}$$

This matrix is diagonalizable with eigenvalues $\lambda_1=1+\sqrt{3},\lambda_2=1-\sqrt{3}$. Writing $P$ under the diagonalized form $M=P\Delta P^{-1}$, with $\Delta=diag(\lambda_1,\lambda_2)$, one obtains:

$$\binom{a_n}{b_n}=P \Delta^n P^{-1}\binom{a_1}{b_1} \ \ \ (4)$$

giving explicit formulas

$$\begin{cases}a_n&=&A \lambda_1^n+B \lambda_2^n\\b_n&=&C \lambda_1^n+D \lambda_2^n\end{cases}$$

with fixed values for $A,B,C,D$ that are to be computed by replacing $P$ and $P^{-1}$ in (4) by their explicit expression.

NB: It is easily seen that, from (2), one can build the following second order recurrence relationship (presented in the first line of the reference that @Robert Israel has given you):

$$a_{n+1}=2a_n+2a_{n-1}$$