Results 1 to 6 of 6

Thread: 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
    $\displaystyle F_{2n}=F_{n}L_{n}$
    where F is a Fibonacci number and L is a Lucas number.
    The farthest I have gotten is:
    $\displaystyle F_{2k+2}=F_{2k+1}+F_{2k}=F_{2k+1}+F_{k}L_{k}$
    I am stuck on how to show that $\displaystyle 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
    678
    Thanks
    1
    Quote Originally Posted by dannyboycurtis View Post
    Hi I am having trouble completing an inductive proof to show that
    $\displaystyle F_{2n}=F_{n}L_{n}$
    where F is a Fibonacci number and L is a Lucas number.
    The farthest I have gotten is:
    $\displaystyle F_{2k+2}=F_{2k+1}+F_{2k}=F_{2k+1}+F_{k}L_{k}$
    I am stuck on how to show that $\displaystyle 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
    22
    Quote Originally Posted by dannyboycurtis View Post
    Hi I am having trouble completing an inductive proof to show that
    $\displaystyle F_{2n}=F_{n}L_{n}$
    where F is a Fibonacci number and L is a Lucas number.
    The farthest I have gotten is:
    $\displaystyle F_{2k+2}=F_{2k+1}+F_{2k}=F_{2k+1}+F_{k}L_{k}$
    I am stuck on how to show that $\displaystyle 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 $\displaystyle F_{n},L_n$ denote the $\displaystyle n$th Fibonacci and Lucas number respectively. Prove that $\displaystyle F_{2n}=F_n L_n$

    Proof:

    Lemma: Let $\displaystyle a_{n}=Aa_{n-1}+Ba_{n-2}$ be a second order homogenous linear recurrence relation. Also, suppose the charctersitic polynomial $\displaystyle x^2-Ax-B$ has real solutions $\displaystyle \alpha,\beta$. Then $\displaystyle a_n=\lambda_1\alpha^n+\lambda_2\beta^n$ where $\displaystyle \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: $\displaystyle a_0=\lambda_1\alpha^0+\lambda_2\beta^0=\lambda_1+\ lambda_2=a_0$.

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

    Inductive step: $\displaystyle 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 $\displaystyle \lambda_1\alpha^{k-2}\left[A\alpha+B\right]+\lambda_2\beta^{k-2}\left[A\beta+B\right]$. Remembering though that $\displaystyle \alpha,\beta$

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

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

    Therefore,

    $\displaystyle 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. $\displaystyle \blacksquare$

    Using this lemma we can easily prove that $\displaystyle 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 $\displaystyle L_n=\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\fra c{1-\sqrt{5}}{2}\right)^n$.

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

    Proof: Just note that

    $\displaystyle F_{n+1}+F_{n-1}=$$\displaystyle \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

    $\displaystyle F_{n+1}+F_{n-1}=$$\displaystyle \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 $\displaystyle \frac{1-\sqrt{5}}{2},\frac{1+\sqrt{5}}{2}$ are solutions to $\displaystyle x^2-x-1=0\implies x^2+1=x+2$, we may shorten our calculations a bit and see that

    $\displaystyle \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,

    $\displaystyle \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

    $\displaystyle F_{n+1}+F_{n-1}=$$\displaystyle \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]$$\displaystyle =\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n=L_n$

    The conclusion follows. $\displaystyle \blacksquare$

    This should help with your induction.

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

    $\displaystyle 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

    $\displaystyle 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
    22
    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
    678
    Thanks
    1
    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 $\displaystyle F_{n},L_n$ denote the $\displaystyle n$th Fibonacci and Lucas number respectively. Prove that $\displaystyle F_{2n}=F_n L_n$

    Proof:

    Lemma: Let $\displaystyle a_{n}=Aa_{n-1}+Ba_{n-2}$ be a second order homogenous linear recurrence relation. Also, suppose the charctersitic polynomial $\displaystyle x^2-Ax-B$ has real solutions $\displaystyle \alpha,\beta$. Then $\displaystyle a_n=\lambda_1\alpha^n+\lambda_2\beta^n$ where $\displaystyle \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: $\displaystyle a_0=\lambda_1\alpha^0+\lambda_2\beta^0=\lambda_1+\ lambda_2=a_0$.

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

    Inductive step: $\displaystyle 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 $\displaystyle \lambda_1\alpha^{k-2}\left[A\alpha+B\right]+\lambda_2\beta^{k-2}\left[A\beta+B\right]$. Remembering though that $\displaystyle \alpha,\beta$

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

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

    Therefore,

    $\displaystyle 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. $\displaystyle \blacksquare$

    Using this lemma we can easily prove that $\displaystyle 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 $\displaystyle L_n=\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\fra c{1-\sqrt{5}}{2}\right)^n$.

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

    Proof: Just note that

    $\displaystyle F_{n+1}+F_{n-1}=$$\displaystyle \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

    $\displaystyle F_{n+1}+F_{n-1}=$$\displaystyle \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 $\displaystyle \frac{1-\sqrt{5}}{2},\frac{1+\sqrt{5}}{2}$ are solutions to $\displaystyle x^2-x-1=0\implies x^2+1=x+2$, we may shorten our calculations a bit and see that

    $\displaystyle \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,

    $\displaystyle \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

    $\displaystyle F_{n+1}+F_{n-1}=$$\displaystyle \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]$$\displaystyle =\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n=L_n$

    The conclusion follows. $\displaystyle \blacksquare$

    This should help with your induction.

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

    $\displaystyle 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

    $\displaystyle 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: Dec 3rd 2011, 12:35 PM
  2. [SOLVED] A Tricky Fibonacci Sequence Identity
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Aug 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: Apr 21st 2010, 09:26 AM
  5. Proving Lucas Numbers and Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 18th 2008, 11:33 PM

Search Tags


/mathhelpforum @mathhelpforum