Intereting Posts

$\sum_{n=1}^{\infty} \frac{1}{(n+1)(n+2)^3}$ using complex analysis
Functions whose derivative is the inverse of that function
$\mathbb R^2$ is not homeomorphic to $\mathbb R^3$.
Categorical Pasting Lemma
Associativity of the smash product on compactly generated spaces
How do I solve a PDE with a Dirac Delta function?
A tensor calculus problem
Is $\sum_{n=1}^\infty \frac{\sin(2n)}{1+\cos^4(n)}$ convergent?
Currently, what is the largest publicly known prime number such that all prime numbers less than it are known?
Determinant from Paul Garrett's Definition of the Characteristic Polynomial.
Help to understand a proof by descent?
Why should we get rid of indefinite integration?
Maximizing/Minimizing triangle area
Local vs global truncation error
Deriving Maclaurin series for $\frac{\arcsin x}{\sqrt{1-x^2}}$.

Solve the recurrence $a_n = 4a_{n−1} − 2 a_{n−2}$

Not sure how to solve this recurrence as I don’t know which numbers to input to recursively solve?

- The sequence $x_{n+1}=\frac{x_n}{2}-\frac{2}{x_n}, x_0>0$ is bounded?
- Find the asymptotic tight bound for $T(n) = 4T(n/2) + n^{2}\log n$
- Solving a set of recurrence relations
- LambertW(k)/k by tetration for natural numbers.
- Strange Recurrence: What is it asymptotic to?
- Recurrence relation for the integral, $ I_n=\int\frac{dx}{(1+x^2)^n} $

- $T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer
- How to calculate $\sum_{n=1}^\infty\frac{(-1)^n}n H_n^2$?
- Simplying linear recurrence sum with binomials
- Question about generating function in an article
- Period of a sequence defined by its preceding term
- Why is solving non-linear recurrence relations “hopeless”?
- What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$,$F(1)=b$ and $a,b>0$?
- Solving a set of recurrence relations
- An issue with approximations of a recurrence sequence
- How many permutations of a multiset have a run of length k?

You can make an “educated guess” and propose the following ansatz: $a_n=p^n$. Your recurrence relation now has the following characteristic equation:

$$p^2-4p+2=0\Longleftrightarrow (p-2-\sqrt{2})(p-2+\sqrt{2})=0$$

Therefore there are two roots, at $p=2\pm\sqrt{2}$, and we get:

$$a_n=\alpha\left(2+\sqrt{2}\right)^n+\beta\left(2-\sqrt{2}\right)^n$$

where $\alpha$ and $\beta$ are constants that can be obtained from the initial conditions. In particular, we have:

$$a_0=\alpha+\beta$$

$$a_1=\alpha\left(2+\sqrt{2}\right)+\beta\left(2-\sqrt{2}\right)$$

This is a system of two equations with two unknowns, that we can solve (it’s a bit tedious though) to get:

$$\beta=\dfrac{a_0\left(2+\sqrt{2}\right)-a_1}{2\sqrt{2}}$$

$$\alpha=a_0-\beta$$

Thus, the explicit expression for $a_n$ is:

$$a_n=\alpha\left(2+\sqrt{2}\right)^n+\beta\left(2-\sqrt{2}\right)^n$$

with $\alpha$ and $\beta$ defined above. (And you can check that it indeed verifies the recurrence relation.)

Hint: Let $r_1,r_2$ be two distinct real roots of the equation

$$

r^2-4r+2

$$

then this recurrence equation has a solution of the form

$$

C_1 r_1^n+C_2 r_2^n

$$

which the constants $C_1,C_2$ can be found by initial values condition.

Assume the solution is $a_n = Ar^n$ then you get:

$$

a_n = Ar^n, a_{n – 1} = A \frac{r^n}{r}, a_{n – 2} = A\frac{r^n}{r^2}

$$

Plug this into your recursion relation:

\begin{align}

a_n = 4a_{n – 1} – 2a_{n – 2}\\

Ar^n = 4A \frac{r^n}{r} – 2A\frac{r^n}{r^2} \\

Ar^n \big(1 – \frac{4}{r} + \frac{2}{r^2}\big) = 0 \\

Ar^n\left(\frac{r^2 – 4r + 2}{r^2}\right) = 0 \\

r^2 – 4r + 2 = 0 \\

r = \frac{4 \pm \sqrt{16 – 8}}{2} = \frac{4 \pm 2\sqrt{2}}{2} = 2 \pm \sqrt{2}

\end{align}

This gives that

$$

a_n = A(2 + \sqrt{2})^n + B(2 – \sqrt{2})^n

$$

It’s worth noting that this is identical to solving a homogeneous linear differential equation.

We can represent this recursion with matrices:

$$

\begin{bmatrix}a_n \\ a_{n-1} \end{bmatrix}

=

\begin{bmatrix}4 & -2 \\ 1 & 0 \end{bmatrix}

\begin{bmatrix}a_{n-1} \\ a_{n-2} \end{bmatrix}

$$

Or $x_n = A\cdot x_{n-1}$ where $x_n$ is the vector specified above. This is a simple difference equation and we can see that

$$

x_n = A^n \cdot x_0

$$

by expanding $x_n = A x_{n-1} = A \cdot A \cdot x_{n-2} = \cdots = A^n \cdot x_0 $

Computing this matrix power is difficult and hard numerically; there’s no easy solution that I know of. To get around this, let’s use eigenvectors $V$ and the matrix of eigenvalues $\Lambda$.

$$

x_n = (V\Lambda V^{-1})^n x_0 = V \Lambda^n V^{-1}x_0

$$

The computation of $\Lambda^n$ is straightforward. $\Lambda$ is diagonal so the computation of this matrix power is just each term raised to a power.

For this $A$,

$$

\begin{aligned}

V &=

\begin{bmatrix}

2+\sqrt{2} & 2-\sqrt{2} \\ 1 & 1

\end{bmatrix}

\\

\Lambda &=

\begin{bmatrix} 2+\sqrt{2} & 0 \\ 0 & 2-\sqrt{2} \end{bmatrix}

=

\begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix}

\end{aligned}

$$

Carrying out this computation, we see that

$$

x_n = \frac{1}{\sqrt{8}}

\begin{bmatrix}

\lambda_1^{n+1} – \lambda_2^{n+1} & \lambda_1^{n+1}\lambda_2 + \lambda_1\lambda_2^{n+1} \\

\lambda_1^n – \lambda_2^n & \lambda_1^n\lambda_2 + \lambda_1 \lambda_2^n

\end{bmatrix}

\cdot x_0

$$

- Showing $x^3$ is not uniformly continuous on $\mathbb{R}$
- Prove the Countable additivity of Lebesgue Integral.
- Inverse Laplace of $ \frac{1}{\sqrt{s} – 1} $?
- Sequence of surjections imply choice
- In a Dedekind domain every ideal is either principal or generated by two elements.
- Connection between eigenvalues and eigenvectors of a matrix in different bases
- Placing the integers $\{1,2,\ldots,n\}$ on a circle ( for $n>1$) in some special order
- Rational function which is bijective on unit disk
- Riemannian Geometry book to complement General Relativity course?
- Degree of a function
- Symmetric and exterior power of representation
- Differential and derivative of the trace of a matrix
- Fourier cosine transforms of Schwartz functions and the Fejer-Riesz theorem
- Density of halting Turing machines
- Mean and Variance of Methods of Moment Estimate and Maximum Likelihood Estimate of Uniform Distribution.