# If $a_0=1$, and $a_n$ is defined by $a_n=a_{n+1}+a_{n+2}$, find $a_n$.

This is not a homework problem, though it is in my textbook as a practice problem that intrigues me enough to try it. I've got some idea how to solve it but I don't know how to prove my hypothesis.

The question reads exactly as follows:

Suppose $a_0,a_1,a_2,a_3,\dots,a_n$ is a sequence of positive real numbers such that $a_0=1$ and $a_n=a_{n+1}+a_{n+2}$, $n\geq 0$. Find $a_n$.

My first idea was to find a pattern to work with. I figured out equations for the first 4 terms in the sequence:

\begin{align} a_0&=1=a_1+a_2=(3a_4+2a_5)+(2a_4+a_5)=5a_4+3a_5\\ a_1&=a_2+a_3=(2a_4+a_5)+(a_4+a_5)=3a_4+2a_5\\ a_2&=a_3+a_4=(a_4+a_5)+a_4=2a_4+a_5\\ a_3&=a_4+a_5 \end{align}

From this, it would appear that the equation for $a_n$ is something of the form $a_n=la_{n+1}+ma_{n+2}$ for some $l,m\in\mathbb{N}$ and some $a_{n+1},a_{n+2}\in\mathbb{R}^{+}$.

Unless I'm wrong, it looks like I can deduce that $a_0$ can be written as a linear combination of two variables $x$ and $y$, and the coefficients $l$ and $m$ appear (though it is unproven) to be coprime. If this is the case, then there should exist an $x$ and $y$ to satisfy the equation $1=lx+my$... But I've only learned how to do this when $x$ and $y$ are restricted to be any value in $\mathbb{Z}$... and I'm clearly restricted to positive real numbers. So how might I be able to tackle this?

• Hint: Find a recurrence relation for $a_n$ in terms of $a_{n-1}$ and $a_{n-2}$ for $n \geq 2$. Then, use strategies from here: en.wikipedia.org/wiki/Recurrence_relation. – Zvi Rosen Sep 24 '13 at 1:22
• Your expression will include a constant which will depend on $a_1$ by the way – L. F. Sep 24 '13 at 1:25
• @Will. Thanks, I can buy that From my point of view, varying $a_1$ gives different plausable answers, but none has a nice closed form. Truly interesting. – Doc Sep 24 '13 at 2:25
• @Will. Great stuff. ;-) – Doc Sep 24 '13 at 2:30
• @WillJagy Ah I had missed the positive condition! :) – L. F. Sep 24 '13 at 11:19

Write it in the usual way with decreasing subscripts as $$a_{n+2} + a_{n+1} - a_n = 0.$$

Whatever you might want to call it is $$\lambda^2 + \lambda - 1 = 0.$$ If this has distinct roots then $a_n = B \lambda_1^n + C \lambda_2^n$ for real or complex constants $B,C$ depending how it turns out.

So, $$\lambda = \frac{-1 \pm \sqrt 5}{2},$$ or $$\lambda_1 = \frac{-1 + \sqrt 5}{2} \approx 0.618, \; \; \lambda_2 = \frac{-1 - \sqrt 5}{2} \approx -1.618.$$

If the coefficient of $\lambda_2$ were nonzero, that term would eventually overwhelm the $\lambda_1$ term, resulting in (eventually) alternating negative and positive $a_n.$ We are told the $a_n$ stay positive forever. So $a_n = B \lambda_1^n.$ Since $a_0 = 1$ we must have $$a_n = \left( \frac{-1 + \sqrt 5}{2} \right)^n.$$

EDIT: it is easy enough to see that the set of sequences solving $a_{n+2} + a_{n+1} - a_n = 0$ make a vector space; you can add two sequences together, you can multiply by a constant, and so on. For differential equations, there is a fair amount involved in showing the dimension of the vector space. But we have difference equations, and the dimension is exactly two, simply because knowing $a_0$ and $a_1$ completely determines the sequence. Put another way, define a basis of two sequences, call them $x,y,$ so $$x_0 = 1, x_1 = 0; \; \; x_{n+2} + x_{n+1} - x_n = 0,$$ $$y_0 = 0, y_1 = 1; \; \; y_{n+2} + y_{n+1} - y_n = 0.$$ Therefore, if I can display two linearly independent sequences (it suffices to check at subscripts $0,1$) then i have another basis.

TUESDAY. Note from comment above: if I had a problem with a repeated root, some constant $\beta$ and sequences solving $$z_{n+2} - 2 \beta z_{n+1} + \beta^2 z_n = 0,$$ my characteristic equation would be $$\lambda^2 - 2 \beta \lambda + \beta^2 = (\lambda - \beta)^2 = 0.$$ A basis, of two sequences is $\{\beta^n, \; n \, \beta^n \}$ so that any specific solution is $$z_n = B \, \beta^n + C \, n \, \beta^n.$$ It's worth checking that both sequences in my basis really work!

• All that is needed is to solve for B and C given the initial conditions and then show that the resulting values satisfy the recurrence. As to how one decides that those equations satisfy the recurrence, that is another matter. But once one does decide this, the verification is straightforward. – marty cohen Sep 25 '13 at 0:14
• btw, I upvoted you since you beat me by 44 seconds. – marty cohen Sep 25 '13 at 0:15
• @martycohen, fair enough. I noticed the wikipedia article goes to arbitrary degree when degree two has very few special cases when the root(s) are real. And voted back... – Will Jagy Sep 25 '13 at 0:24

$a_n=a_{n+1}+a_{n+2}$, or $a_{n+2} = -a_{n+1}+a_{n}$.

As usual, let $a_n = c^n$. Then $c^{n+2} = -c^{n+1}+c^n$ or $c^2 = -c+1$ or $c^2+c=1$.

$c^2+c+1/4=5/4$ or $(c+1/2)^4 = 5/4$ or $c = -1/2 \pm \sqrt{5}/2 =\dfrac{-1 \pm \sqrt{5}}{2}$.

Let $c_1 = \dfrac{-1 + \sqrt{5}}{2}$ and $c_2 = \dfrac{-1 - \sqrt{5}}{2}$.

All solutions are of the form $uc_1^n+vc_2^n$. Since $a_0 = 1$, $1 = u+v$.

Since $|c_1| < 1$ and $|c_2| > 1$, for all the terms to be positive, $c_2$ must not contribute at all, or else there would be terms of arbitrarily large positive and negative values. This means that $v = 0$.

Therefore $u = 1$ and the series is $a_n = c_1^n$.

• Why do you know that all solutions have that form? I think it might be some well known result, but I would like to know where does this come from. – chubakueno Sep 24 '13 at 3:24
• @chubakueno the solution sets of linear recurrence relations from a vector space. Here it is of dimension two as it takes only two initial terms to uniquely determine a solution. We can then take two linearly independent solutions and be sure they generate the entire space, – oldrinb Sep 24 '13 at 5:17