Intereting Posts

Longest antichain of divisors
Cyclic rearrangements of periods of the decimal expansions of certain rationals
Be $f:\;(a,b)\rightarrow\mathbb{R}$ a continuous function. Suppose $c\in(a,b)$ …
When chessboards meet dominoes
Probability of at least one king and at least one ace when 5 cards are lifted from a deck?
Leibniz rule and Derivations
Maximum area of a rectangle inscribed in a triangle is $1/2$ the area of triangle
Valuation rings and total order
Cardinal equalities: $\aleph_0^\mathfrak c=2^\mathfrak c$
$ x^2 + \frac {x^2}{(x-1)^2} = 2010 $
Why are addition and multiplication included in the signature of first-order Peano arithmetic?
Limit with Integral and Sigma
Proof that $\mathbb{R}$ is not a finite dimensional vector space
What is the difference between probability and statistics?
Is the closure of path-connected set path connected?

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?

- How to get the characteristic equation?
- About the positive sequence $a_{n+2} = \sqrt{a_{n+1}} + \sqrt{a_n}$
- Solving two-dimensional recurrence relations
- How to evaluate $\lim_{ n\to \infty }\frac{a_n}{2^{n-1}}$, if $a_0=0$ and $a_{n+1}=a_n+\sqrt{a_n^2+1}$?
- Convergence of sequence given by $x_1=1$ and $x_{n+1}=x_n+\sqrt{x_n^2+1}$
- Show that there is a unique sequence of positive integers $(a_n)$ satisfying $a_1=1,a_2=2,a_4=12,a_{n+1}a_{n-1}=a_n^2\pm 1 $

- Linear homogeneous recurrence relations with repeated roots; motivation behind looking for solutions of the form $nx^n$?
- Fibonacci General Formula - Is it obvious that the general term is an integer?
- Induction with floor, ceiling $n\le2^k\implies a_n\le3\cdot k2^k+4\cdot2^k-1$ for $a_n=a_{\lfloor\frac{n}2\rfloor}+a_{\lceil\frac{n}2\rceil}+3n+1$
- Proof Using the Monotone Convergence Theorem for the sequence $a_{n+1} = \sqrt{4 + a_n}$
- Links between difference and differential equations?
- Combinatorial interpretation of Delannoy numbers formula
- Repertoire Method Clarification Required ( Concrete Mathematics )
- Integer partition of n into k parts recurrence
- Find limit $a_{n + 1} = \int_{0}^{a_n}(1 + \frac{1}{4} \cos^{2n + 1} t)dt,$
- What is the most elementary way of proving a sequence is free of non-trivial squares?

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

$$

- If $xy$ and $x+y$ are both even integers (with $x,y$ integers), then $x$ and $y$ are both even integers
- How to geometrically prove the focal property of ellipse?
- REVISITED $^2$: Does a solution in $\mathbb{R}^n$ imply a solution in $\mathbb{Q}^n$?
- Method of proof of $\sum\limits_{n=1}^{\infty}\tfrac{\coth n\pi}{n^7}=\tfrac{19}{56700}\pi^7$
- An integration of product $(1-x^n)$
- $\lim\limits_{n\to\infty} \frac{n}{\sqrt{n!}} =e$
- Direct proof that $n!$ divides $(n+1)(n+2)\cdots(2n)$
- Prove that $\frac{a_1^2}{a_1+a_2}+\frac{a_2^2}{a_2+a_3}+ \cdots \frac{a_n^2}{a_n+a_1} \geq \frac12$
- If a and b are odd integers, then $8\mid (a^2-b^2)$
- How does backwards induction work to prove a property for all naturals?
- square root of symmetric matrix and transposition
- Distribution of Stopped Brownian motion at hitting time of another Brownian motion.
- König's Infinity Lemma and Aronszajn Trees
- The equivalent definition of $W_0^{1,\infty}(\Omega)$
- Simplification of $\binom{50}{0}\binom{50}{1}+\binom{50}{1}\binom{50}{2}+\cdots+\binom{50}{49}\binom{50}{50}$