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?
 A: 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!
A: $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$.
