I was wondering how can we prove that a recurrence relationship depending on the two previous terms is actually the sum of two geometric sequences

Question

I was working on a problem and I stumbled upon this equality:

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

And I'm trying to find the general expression of the sequence $a$.

For this, I wanted to show that $a$ can just be expressed as the sum of two geometric sequence so that I can rewrite this equality using the general expression of geometric sequences:

Edit: $q {\neq} 0$

$a_0*q^{n+2} = a_0*q^{n+1} + a_0*q^{n}$

but I didn't manage to prove that.

Could someone help me please

Answer 1

Second-order linear relations with constant coefficients are very well-documented problems.

In your case, the equation can be rewritten : $$a_{n+2} - a_{n+1} - a_n = 0$$

You need to study the characteristic polynomial equation $P(X) = X^2 - X - 1 = 0$. This one has two roots: $\varphi = \frac{1 + \sqrt 5}{2}$ and $\bar \varphi = \frac{1 - \sqrt 5}{2}$. (Note that $\varphi$ is the “golden ratio”.) Then, all the solutions to your recurrence relation are the sequences of form: $$a_n = A \varphi^n + B \bar\varphi^n$$ with $A, B \in \mathbf R$.

The values of $A$ and $B$ depend on your initial conditions.

Answer 2

Let $a,b$ be the roots of $$px^2+qx+r=0.....(1)$$ Then $$pa^2+qa+r=0$$ $$\implies Cpa^{n+2}+Cqa^{n+1}+Cra^n=0$$ Similarly, we have $$Dpb^{n+2}+Dqb^{n+1}+Drb^n=0$$ Adding these two equations, we get $$p(C a^{n+2}+D a^{n+2})+q(Ca^{n+1}+Db^{n+1})+r(Ca^n+Db^n)=0.$$ Introduce $$A_n=C a^n+D b^n.....(2)$$ Then we can write $$pA_{n+2}+qA_{n+1}+rA_n=0.....(3)$$

Finally (2) is the general solution (sum of two GPs) of the recurrence relation (3), where $a,b$ are the roots of (1) and $C,D$ are two arbitrary paramwteres to be determined by the given initial values.

Answer 3

OK, now a solution if you do not assume the theorem about the closed form of recurrent linear sequences of order 2.

Consider any sequence $(u_n)_n$ such that $u_{n+2} = a u_{n +1} + b u_n$. Assume that polynomial $X^2 - a X - b$ has two complex roots $\alpha \neq \beta \in \mathbf C$.

We want to prove that there exists $\lambda, \mu \in \mathbf C$ such that for all $n \in \mathbf N$, $$ u_n = \lambda \alpha^n + \mu \beta^n$$

Necessary condition. For $n = 0$, one needs have $u_0 = \lambda + \mu$. For $n = 1$, one needs have $u_1 = \lambda \alpha + \mu \beta$. As $\alpha \neq \beta$, this system of equations has a single solution: $$\lambda = \frac{u_1 - \beta u_0}{\alpha - \beta}, \quad \mu = \frac{u_1 - \alpha u_0}{\beta - \alpha}$$

Sufficient condition. Now, we need to prove that the sequence: $$u_n = \lambda \alpha^n + \mu \beta^n$$ with $\lambda = \frac{u_1 - \beta u_0}{\alpha - \beta}$ and $\mu = \frac{u_1 - \alpha u_0}{\beta - \alpha}$ satisfies the recurrence condition. This can be proven by recurrence.

Indeed, the equality is matched for $n = 0$ and $n = 1$. Assume it is matched for some $n$ and for $n+1$. Then, at rank $n+2$: $$u_{n+2} = a u_{n+1} + b u_n$$ As the equality is assumed for ranks $n$ and $n+1$, $$u_{n+2} = a (\lambda \alpha^{n+1} + \mu \beta^{n+1}) + b(\lambda \alpha^n + \mu \beta^n)$$ $$u_{n+2} = \lambda \alpha^n (a \alpha + b) + \mu \beta^n (a \beta + b)$$ As $\alpha$ and $\beta$ are solutions to $X^2 = aX + b$, we have: $$u_{n+2} = \lambda \alpha^n \alpha^2 + \mu \beta^n \beta^2$$ $$u_{n+1} = \lambda \alpha^{n+2} + \mu \beta^{n+2}$$

This proves the equality at rank $n+2$. By recurence, for every $n \in \mathbf N$, one has: $$u_n = \lambda \alpha^n + \mu \beta^n.$$

QED.