fibonacci/lucas identity help

**dannyboycurtis** · December 2nd 2009, 06:08 PM

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?

**aman_cc** · December 2nd 2009, 07:34 PM

Originally Posted by dannyboycurtis

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

**Drexel28** · December 2nd 2009, 07:54 PM

Originally Posted by dannyboycurtis

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

**Drexel28** · December 2nd 2009, 07:55 PM

Originally Posted by aman_cc

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?

**aman_cc** · December 2nd 2009, 10:00 PM

Originally Posted by Drexel28

I am not sure what you know, so I will do a few lemmas for you.

Problem: Let $F_{n},L_n$ denote the $n$ th 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

**dannyboycurtis** · December 3rd 2009, 06:34 PM

thank you all for the help.

Thread: fibonacci/lucas identity help

LinkBack

Thread Tools

Display

fibonacci/lucas identity help

Similar Math Help Forum Discussions

Fibonacci sequence identity

[SOLVED] A Tricky Fibonacci Sequence Identity

Lucas Sequences

Proof about Fibonacci and Lucas numbers (GCD)

Proving Lucas Numbers and Fibonacci Numbers

Search Tags