1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is the Fibonacci sequence starting at the 2nd term. $\endgroup$ – nathan.j.mcdougall Nov 14 '17 at 18:35
  • 1
    $\begingroup$ @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. $\endgroup$ – JMoravitz Nov 14 '17 at 18:36
  • $\begingroup$ Sure. I just thought it could be useful as a comment. :) $\endgroup$ – nathan.j.mcdougall Nov 14 '17 at 18:37
  • $\begingroup$ yes but my formula which i derived is not true . I am not sure $\endgroup$ – M. A. SARKAR Nov 14 '17 at 18:37
  • 1
    $\begingroup$ 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$. $\endgroup$ – JMoravitz Nov 14 '17 at 18:48
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Not true because according to you $ \ a_3=F_2a_2+F_1a_1=2a_2+a_1 \ $ , which is not true $\endgroup$ – M. A. SARKAR Nov 14 '17 at 18:39
  • $\begingroup$ @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. $\endgroup$ – JMoravitz Nov 14 '17 at 18:43
  • 1
    $\begingroup$ $$ \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}}$$ $\endgroup$ – Guy Fsone Nov 14 '17 at 21:09
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.