fibonacci identity

ratm

New member
Joined
May 1, 2007
Messages
10
Prove the identity where Fn is the n-th Fibonacci number.

[n 0)*F0 + (n 1)*F1 + (n 2)*F2 + (n 3)*F3 +. . .+ (n n)*Fn = F2n


(n 0) = n choose 0...etc
and F0 = F sub 0...etc
 
What have you done for yourself on this problem?
Do you know how to use mathematical induction?
At least show that this is true for n=0 & n=1!
 
Yes I do, although I do struggle with it at times and this is the case here.
I have done proofs involving different identities of n choose k and fibonacci but not with them together like this. I just can't seem finish it using induction.
 
ratm said:
Yes I do, although I do struggle with it at times and this is the case here. I have done proofs involving different identities of n choose k and fibonacci but not with them together like this. I just can't seem finish it using induction.

Show us the cases: n=0 & n=1.
 
n=0

LHS= (n 0)*F0 RHS= F2n

=(0 0)*F0 =F2(0)
=F0
=0!/0!*(0-0)! =0
=1*F0
=1*0
=0 0=0

n=1

now in this situation i am not sure when it says n=1 i assume it means
(n 0)*F0 and (n 1)*F1 added which is 1

LHS=0+(1 1)*F1 RHS=F2n
=0+1!/1!*(1-1)! = F2(1)
=0+1 =F2
=1 =1
1=1
 
Here is n=1:
\(\displaystyle \L\left( {\begin{array}{c}
1 \\
0 \\
\end{array}} \right)F_0 + \left( {\begin{array}{c}
1 \\
1 \\
\end{array}} \right)F_1 = 1 \cdot F_0 + 1 \cdot F_1 = 2 = F_2 .\)
 
i know that

(1 0) = 1
F0=0
(1 1)=1
F1=1

but according to your last post F0 would have to equal 1 to make n=1, 2.

bc 1*F0 + 1*F1 = 1*0 + 1*1 = 1 not 2

am i missing something
[/quote]
 
The actual historical Fibonacci sequence is: 1,1,2,3,5,… .
I suppose some textbooks could begin the sequence with 0.
What does your textbook do?

I will tell you that it makes absolutely no difference to this problem.
The general induction step is exactly the same.
 
ok well that makes sense then

mine book says F0=0, F1=1 F2=1 and so on
 
ratm said:
ok well that makes sense then
mine book says F0=0, F1=1 F2=1 and so on
BUT still it makes absolutely no difference to this problem
 
anyway that portion is not the problem

i used n=n+1

Indution Hyp.

suppose (n+1 0)F0 + (n+1 1)F1 + (n+2)F2 +..+(n+1 n+1)Fn+1=F2n+1

LHS
={(n+1 0)F0 + (n+1 1)F1 + (n+1 2)F2 +...+(n+1 n+1)Fn}+(n n)Fn

RHS
=F2n+1 + (n n)Fn

but I do not know how to get the RHS to F2n
 
PKA

I'd really appreciate it if you could give a look to my other question titled
"Number Theory". It is from a Discrete Math class not number theory, but my professor says this section is a precursor. This problem comes from a section of Primes Divisors and Integers. We haven't really worked anything like this so I am not sure where to begin.
 
Top