# 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 \$.

$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 .

• This is the Fibonacci sequence starting at the 2nd term. – nathan.j.mcdougall Nov 14 '17 at 18:35
• @nathan.j.mcdougall you misread the question. The OP wishes to describe any fibonacci-like sequence in terms of the fibonacci numbers and the initial two terms of the sequence. – JMoravitz Nov 14 '17 at 18:36
• Sure. I just thought it could be useful as a comment. :) – nathan.j.mcdougall Nov 14 '17 at 18:37
• yes but my formula which i derived is not true . I am not sure – M. A. SARKAR Nov 14 '17 at 18:37
• The fibonacci sequence is more commonly defined with two ones to start or with a zero and a one to start, making the sequence $1,1,2,3,5,8,13,\dots$ or $0,1,1,2,3,5,8,13,\dots$. Which of these numbers you decide is $F_1$, be it the first one, the second one, or the zero, is a matter of taste. Most commonly in combinatorics and computer science, we define $F_0$ to be the zero, $F_1$ to be the first one $F_2$ to be the second one and so on... In the way your problem defined the sequence this would be $F_1$ corresponding to the second one. We can extend the sequence to include $F_0=1$. – JMoravitz Nov 14 '17 at 18:48

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*}

• Not true because according to you $\ a_3=F_2a_2+F_1a_1=2a_2+a_1 \$ , which is not true – M. A. SARKAR Nov 14 '17 at 18:39
• @yourmath you misread or misinterpreted his statement. $a_3=a_{2+1}=F_{2-1}a_2+F_{2-2}a_1=F_1a_2+F_0a_1=1a_2+1a_1=a_2+a_1$ as expected, remembering that we can define $F_0=1$ to extend the sequence in the other direction. If that is unsatisfactory, then just explicitly state that $a_3=a_2+a_1$ and use your formula for the rest of the values of $n$ greater than or equal to four. – JMoravitz Nov 14 '17 at 18:43
• $$\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}}$$ – Guy Fsone Nov 14 '17 at 21:09

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.

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}}$$

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$.)