Results 1 to 6 of 6

Math Help - fibonacci/lucas identity help

  1. #1
    Member
    Joined
    Sep 2009
    Posts
    104

    fibonacci/lucas identity help

    Hi I am having trouble completing an inductive proof to show that
    F_{2n}=F_{n}L_{n}
    where F is a Fibonacci number and L is a Lucas number.
    The farthest I have gotten is:
    F_{2k+2}=F_{2k+1}+F_{2k}=F_{2k+1}+F_{k}L_{k}
    I am stuck on how to show that F_{2k+2}=F_{k+1}L_{k+1}
    Any suggestions?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by dannyboycurtis View Post
    Hi I am having trouble completing an inductive proof to show that
    F_{2n}=F_{n}L_{n}
    where F is a Fibonacci number and L is a Lucas number.
    The farthest I have gotten is:
    F_{2k+2}=F_{2k+1}+F_{2k}=F_{2k+1}+F_{k}L_{k}
    I am stuck on how to show that F_{2k+2}=F_{k+1}L_{k+1}
    Any suggestions?

    Hi - I haven't tried it but may be an easier approach is use/proof following two

    1. L(n) = F(n-1) + F(n+1)
    2. F(2n) = F(n).(F(n-1) + F(n+1))

    I think (2) has been proved in this forum earlier
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by dannyboycurtis View Post
    Hi I am having trouble completing an inductive proof to show that
    F_{2n}=F_{n}L_{n}
    where F is a Fibonacci number and L is a Lucas number.
    The farthest I have gotten is:
    F_{2k+2}=F_{2k+1}+F_{2k}=F_{2k+1}+F_{k}L_{k}
    I am stuck on how to show that F_{2k+2}=F_{k+1}L_{k+1}
    Any suggestions?
    I am not sure what you know, so I will do a few lemmas for you.

    Problem: Let F_{n},L_n denote the nth Fibonacci and Lucas number respectively. Prove that F_{2n}=F_n L_n

    Proof:

    Lemma: Let a_{n}=Aa_{n-1}+Ba_{n-2} be a second order homogenous linear recurrence relation. Also, suppose the charctersitic polynomial x^2-Ax-B has real solutions \alpha,\beta. Then a_n=\lambda_1\alpha^n+\lambda_2\beta^n where \begin{cases}\lambda_1+\lambda_2=a_0 \\ \lambda_1\alpha+\lambda_2\beta=a_1\end{cases}.

    Proof: We do this by strong induction induction.

    Base case: a_0=\lambda_1\alpha^0+\lambda_2\beta^0=\lambda_1+\  lambda_2=a_0.

    Inductive hypothesis: Assume that a_n=\lambda_1\alpha^n+\lambda_2\beta^n for all n<k

    Inductive step: a_{k}=Aa_{k-1}+Ba_{k-2}\overbrace{=}^{\text{IH}}A\lambda_1\alpha^{k-1}+A\lambda_2\beta^{k-1}+B\lambda_1\alpha^{k-2}+B\lambda_2\beta^{k-2}. From here a little manipulation yields \lambda_1\alpha^{k-2}\left[A\alpha+B\right]+\lambda_2\beta^{k-2}\left[A\beta+B\right]. Remembering though that \alpha,\beta

    are both solutions to x^2-Ax-B=0 we see that

    \alpha^2-A\alpha-B=0\implies \alpha^2=A\alpha+B and \beta^2-A\beta-B=0\implies \beta^2=A\beta+B.

    Therefore,

    a_k=\lambda_1\alpha^{k-2}\left[A\alpha+B\right]+\lambda_2\beta^{k-2}\left[A\beta+B\right]=\lambda_1\alpha^{k-2}\cdot\alpha^2+\lambda_2\beta^{k-2}\cdot\beta^2=\lambda_1\alpha^k+\lambda_2\beta^k

    This completes the induction. \blacksquare

    Using this lemma we can easily prove that F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\r  ight)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n and L_n=\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\fra  c{1-\sqrt{5}}{2}\right)^n.

    Lemma: L_n=F_{n+1}+F_{n-1}.

    Proof: Just note that

    F_{n+1}+F_{n-1}= \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right  )^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}+\frac{1}{\sqrt{5}}\left(  \frac{1+\sqrt{5}}{2}\right)^{n-1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}

    Grouping the terms and factoring out common stuff gives

    F_{n+1}+F_{n-1}= \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right  )^{n-1}\left[\left(\frac{1+\sqrt{5}}{2}\right)^2+1\right]-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\left[\left(\frac{1-\sqrt{5}}{2}\right)^2+1\right].
    Realizing though that \frac{1-\sqrt{5}}{2},\frac{1+\sqrt{5}}{2} are solutions to x^2-x-1=0\implies x^2+1=x+2, we may shorten our calculations a bit and see that

    \left(\frac{1+\sqrt{5}}{2}\right)^2+=\frac{1+\sqrt  {5}}{2}+2=\frac{5+\sqrt{5}}{2}=\sqrt{5}\cdot\frac{  1+\sqrt{5}}{2}.

    Similarly,

    \left(\frac{1-\sqrt{5}}{2}\right)^2+1=\frac{1-\sqrt{5}}{2}+2=\frac{5-\sqrt{5}}{2}=\sqrt{5}\cdot\frac{\sqrt{5}-1}{2}=-\sqrt{5}\cdot\frac{1-\sqrt{5}}{2}

    Utilizing this we may finally see that

    F_{n+1}+F_{n-1}= \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right  )^{n-1}\left[\left(\frac{1+\sqrt{5}}{2}\right)^2+1\right]-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\left[\left(\frac{1-\sqrt{5}}{2}\right)^2+1\right] =\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n=L_n

    The conclusion follows. \blacksquare

    This should help with your induction.

    Remark: In fact, to end the proof without induction merely note that:

    F_{2n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{2n}-\left(\frac{1-\sqrt{5}}{2}\right)^{2n}\right]

    And using the difference of squares identity we see that

    F_{2n}=\overbrace{\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]}^{F_n}\cdot\overbrace{\left[\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n\right]}^{L_n}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by aman_cc View Post
    Hi - I haven't tried it but may be an easier approach is use/proof following two

    1. L(n) = F(n-1) + F(n+1)
    2. F(2n) = F(n).(F(n-1) + F(n+1))

    I think (2) has been proved in this forum earlier
    Great minds think alike, huh?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Drexel28 View Post
    I am not sure what you know, so I will do a few lemmas for you.

    Problem: Let F_{n},L_n denote the nth Fibonacci and Lucas number respectively. Prove that F_{2n}=F_n L_n

    Proof:

    Lemma: Let a_{n}=Aa_{n-1}+Ba_{n-2} be a second order homogenous linear recurrence relation. Also, suppose the charctersitic polynomial x^2-Ax-B has real solutions \alpha,\beta. Then a_n=\lambda_1\alpha^n+\lambda_2\beta^n where \begin{cases}\lambda_1+\lambda_2=a_0 \\ \lambda_1\alpha+\lambda_2\beta=a_1\end{cases}.

    Proof: We do this by strong induction induction.

    Base case: a_0=\lambda_1\alpha^0+\lambda_2\beta^0=\lambda_1+\  lambda_2=a_0.

    Inductive hypothesis: Assume that a_n=\lambda_1\alpha^n+\lambda_2\beta^n for all n<k

    Inductive step: a_{k}=Aa_{k-1}+Ba_{k-2}\overbrace{=}^{\text{IH}}A\lambda_1\alpha^{k-1}+A\lambda_2\beta^{k-1}+B\lambda_1\alpha^{k-2}+B\lambda_2\beta^{k-2}. From here a little manipulation yields \lambda_1\alpha^{k-2}\left[A\alpha+B\right]+\lambda_2\beta^{k-2}\left[A\beta+B\right]. Remembering though that \alpha,\beta

    are both solutions to x^2-Ax-B=0 we see that

    \alpha^2-A\alpha-B=0\implies \alpha^2=A\alpha+B and \beta^2-A\beta-B=0\implies \beta^2=A\beta+B.

    Therefore,

    a_k=\lambda_1\alpha^{k-2}\left[A\alpha+B\right]+\lambda_2\beta^{k-2}\left[A\beta+B\right]=\lambda_1\alpha^{k-2}\cdot\alpha^2+\lambda_2\beta^{k-2}\cdot\beta^2=\lambda_1\alpha^k+\lambda_2\beta^k

    This completes the induction. \blacksquare

    Using this lemma we can easily prove that F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\r  ight)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n and L_n=\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\fra  c{1-\sqrt{5}}{2}\right)^n.

    Lemma: L_n=F_{n+1}+F_{n-1}.

    Proof: Just note that

    F_{n+1}+F_{n-1}= \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right  )^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}+\frac{1}{\sqrt{5}}\left(  \frac{1+\sqrt{5}}{2}\right)^{n-1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}

    Grouping the terms and factoring out common stuff gives

    F_{n+1}+F_{n-1}= \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right  )^{n-1}\left[\left(\frac{1+\sqrt{5}}{2}\right)^2+1\right]-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\left[\left(\frac{1-\sqrt{5}}{2}\right)^2+1\right].
    Realizing though that \frac{1-\sqrt{5}}{2},\frac{1+\sqrt{5}}{2} are solutions to x^2-x-1=0\implies x^2+1=x+2, we may shorten our calculations a bit and see that

    \left(\frac{1+\sqrt{5}}{2}\right)^2+=\frac{1+\sqrt  {5}}{2}+2=\frac{5+\sqrt{5}}{2}=\sqrt{5}\cdot\frac{  1+\sqrt{5}}{2}.

    Similarly,

    \left(\frac{1-\sqrt{5}}{2}\right)^2+1=\frac{1-\sqrt{5}}{2}+2=\frac{5-\sqrt{5}}{2}=\sqrt{5}\cdot\frac{\sqrt{5}-1}{2}=-\sqrt{5}\cdot\frac{1-\sqrt{5}}{2}

    Utilizing this we may finally see that

    F_{n+1}+F_{n-1}= \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right  )^{n-1}\left[\left(\frac{1+\sqrt{5}}{2}\right)^2+1\right]-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\left[\left(\frac{1-\sqrt{5}}{2}\right)^2+1\right] =\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n=L_n

    The conclusion follows. \blacksquare

    This should help with your induction.

    Remark: In fact, to end the proof without induction merely note that:

    F_{2n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{2n}-\left(\frac{1-\sqrt{5}}{2}\right)^{2n}\right]

    And using the difference of squares identity we see that

    F_{2n}=\overbrace{\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]}^{F_n}\cdot\overbrace{\left[\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n\right]}^{L_n}
    @dannyboycurtis:

    Lemma:

    This can also be proved rather easily using induction.
    Using the following equivalent form of induction - assume the proposition is true for all k<=n; use this to prove it holds for k=n+1
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2009
    Posts
    104
    thank you all for the help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci sequence identity
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 3rd 2011, 12:35 PM
  2. [SOLVED] A Tricky Fibonacci Sequence Identity
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 21st 2010, 08:24 PM
  3. Lucas Sequences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 21st 2010, 06:21 AM
  4. Proof about Fibonacci and Lucas numbers (GCD)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 21st 2010, 09:26 AM
  5. Proving Lucas Numbers and Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 18th 2008, 11:33 PM

Search Tags


/mathhelpforum @mathhelpforum