find the formula of $ \ a_n \ $ in terms of $ a_1, \ a_2 \ and \ \ F_n \ $. Let $ F_n=\{1,2,3,5,8,................ \} \ \ with \ \ F_n=F_{n-1}+F_{n-2} , \ \ F_1=1, \ F_2=2 $ 
Also consider the sequence $ \ a_n=a_{n-1}+a_{n-2} \ $ 
Then find the formula of $ \ a_n \ $ in terms of $ a_1, \ a_2 \ and \ \ F_n \ $. 
My Answer:
$ a_3=a_2+a_1 \\ a_4=2a_2+a_1 \\ a_5=3a_2+2a_1 \\ a_6=5a_2+3a_1 \\ a_7=8a_2+5a_1 \ $
Thus I think , 
$ a_n=F_{n-2} a_2+F_{n-3} a_1 \ $
But not all is satisfying . 
Please help me out.
 A: Prove by induction, just induction step from $n,n-1$ to $n+1$ 
\begin{eqnarray*}
a_{n+1}&=& a_n+a_{n-1}\\
&=& F_{n-2} a_2+F_{n-3} a_1  + F_{n-3} a_2+F_{n-4} a_1\\
&=&  (F_{n-2}+ F_{n-3}) a_2+(F_{n-3}+ F_{n-4}) a_1\\
&=&  F_{n-1} a_2+F_{n-2} a_1
\end{eqnarray*}
A: 
Answer:proof without induction for every $n\ge 3$ we have,
  $$\color{blue}{a_n= a_2 F_{n-2} +a_1F_{n-3}  }$$ See the details below

Both recursive relations , $$F_n=F_{n-1}+F_{n-2} , ~~~~\text{and}~~~~~ a_n=a_{n-1}+a_{n-2} $$
have the same characteristic equation which is, $x^2 = x+1$ whose roots are $$ 
\phi=\frac{\sqrt 5+1}{2}~~~\text{and}~~~\psi=\frac{1-\sqrt 5}{2}$$
Hence, one can easily check  that $a_n$ and $F_n$ have the form , $$ a_n =c\phi^{n-1}+k\psi^{n-1} = \color{red}{\frac{1}{\sqrt 5}\left((a_2-a_1\psi)\phi^{n-1}+(a_1\phi -a_2)\psi^{n-1}\right)}$$
Namely solving $ a_1 = c+k~~~\text{and}~~~a_2 =c\phi+k\psi$n we get, 
$$c= \frac{1}{\sqrt 5}(a_2-a_1\psi)~~~\text{and}~~~~k=\frac{1}{\sqrt 5}(a_1\phi -a_2) $$
 Check that by yourself using the remark below is should not cause any difficulty 
On the other hand, tt is well known that (you might prove by induction that) 
$$ F_n = \frac{1}{\sqrt 5}(\phi^{n+1}-\psi^{n+1})$$

Remark(check that): $\phi\cdot\psi = -1$  and $\phi^2 =\phi+ 1$ and $\phi +2 = \sqrt 5\phi$ these imply that, 

$$\phi F_n =  \frac{1}{\sqrt 5}(\phi^{n+2}+\psi^{n}) =\frac{1}{\sqrt 5}(\phi^{n}(\phi+1)+\psi^{n})   $$
and $$ F_{n-1} =  \frac{1}{\sqrt 5}(\phi^{n}-\psi^{n}) $$
Hence, adding the previous two relations we get 
$$ \color{blue }{\phi^{n+1} = \phi F_n +F_{n-1} \implies \phi^{n-1} = \phi F_{n-2} +F_{n-3}}$$
Similar reasoning shows that
$$ \color{blue }{\psi^{n-1} = -\psi F_{n-2} -F_{n-3}}$$
Replacing in the red expression above we obtain  .
$$ \color{red}{a_n= \frac{1}{\sqrt 5}\left((a_2-a_1\psi)(\phi F_{n-2} +F_{n-3})+(a_1\phi -a_2)(\psi F_{n-2} +F_{n-3})\right)}\\=\frac{1}{\sqrt 5}\left(a_2 F_{n-2}(\phi-\psi) +a_1F_{n-3}) (\phi-\psi))\right) \\\color{blue}{=a_2F_{n-2} +a_1F_{n-3}}$$
A: You've done all of the hard work — you've conjectured the correct formula. 
Now, what you do is forget the original problem, and try to carry out the new exercise

Let $a$ be a sequence satisfying $a_n = a_{n-1} + a_{n-2}$. Prove that $a_n = F_{n-2} a_2 + F_{n-3} a_1$.

You've (presumably) solved a lot of problems of this type. This one should not be unusual in any fashion; use the same methods as you would any similar problem! Induction, for example.
A lot of math is of this general form; when given a complicated problem, find ways to reduce it (or parts of it) to simpler problems that you know how to solve, and then solve them.
A: Consider the generalized Fibonacci sequence $f_n=af_{n-1}+bf_{n-2}$. The characteristic roots are given by
$$\alpha,\beta=\frac{a+\sqrt{a^2+4b}}{2}$$
and the general solution can be expressed as
$$f_n=f_1G_n+bf_0G_{n-1}$$
where
$$G_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}$$
Specializing to your case, we have $\alpha,\beta=\varphi,\psi$ and by your definition of $F$, $G_n=F_{n-2}$, that is a shifted Fibonacci sequence. Thus, the solution, as you correctly surmised is given by
$$a_n=F_{n-2} a_1+F_{n-3} a_0$$
(Note that I have indexed $a$ and $G$ from $n=0$.)
