Author 
Message 
Matthew Roozee science forum beginner
Joined: 22 Oct 2005
Posts: 7

Posted: Mon Oct 24, 2005 7:52 am Post subject:
Re: Binomial Coefficients and Fibonacci



Doug Mitchell wrote:
Quote:  I think to be rigorously prove the following relationship:
SUM[k=0 to n; C(n,k) F_k] = F_{2n} where F_k is the kth Fibonacci term
I would need to use....induction?
Well I see that it holds for n=1, or 2
And I think the 'induction hypothesis' would be SUM [k=0 to n; C(n.k)
F_k]=F_{2n}?
And to complete the proof it now needs to be shown that the relationship
hold in the "n+1" case?
i.e. SUM [k=0 to n+1; C(n+1.k) F_k]=F_{2(n+1)} ??
I dont see how I can use the induction hypothesis to prove this "n+1" case.

I apologize in advance for the unreadability of the proof below. I have
begun with an example to show the ideas behind the proof and then
constructed the proof but the notation is cumbersome.
Consider F_10.
F_10 = F_9 + F_8 (by the definition of the Fibonacci Sequence)
Similarly, F_9 = F_8 + F_7 and F_8 = F_7 + F_6
Summing these gives: F_10 = F_8 + 2F_7 + F_6
Repeating this decomposition:
F_8 = F_7 + F_6; 2F_7 = 2F_6 + 2F_5; F_6 = F_5 + F_4 or
F_10 = F_7 + 3F_6 + 3F_5 + F_4
And now we start to see a familiar pattern. The coefficients look like
a bunch of "n Choose k"'s. The next two iterations will give:
F_10 = F_6 + 4F_5 + 6F_4 + 4F_3 + F_2 and
F_10 = F_5 + 5F_4 + 10F_3 + 10F_2 + 5F_1 + F_0
This last expansion is just the identity you stated for n = 5.
So what is going on? The coefficients form a sort of shifting Pascal's
Triangle (whose entries are n choose k's). The highest Fibonnaci in
each successive expansion is 1 less than the highest in the previous
expansion and the lowest Fibonacci is 2 less than the lowest in the
previous expansion. So when iterate 5 times, the low end has gone from
10 down to 0 and the high end has gone from 10 down to 5 at which point
we have your identity.
So let's try to formalize this into a proof.
What we will prove is:
[1] F_N = SUM[k=0 to j; C(j,k)F_{N2j+k}]
for j <= N/2
Once we succeed in proving [1], we let N = 2n and j = n and we get:
SUM[k=0 to n; C(n,k)F_k] = F_2n establishing the desired identity.
So how do we prove [1]? For this, we will use induction on j.
For any N, if F_N = SUM[k=0 to j; C(j,k)F_{N2j+k}] for j+1 <= N/2 then
F_N = SUM[k=0 to j+1; C(j+1,k)F_{N2(j+1)+k}]
First, observe that when j+1 <= N/2, N2(j+1)+k > 0 so the Fibonacci
term is defined for all of our k's so long as j+1 <= N/2. That is, we
won't get into trouble by trying to describe F_1 = F_0 + F_{1}.
Second, observe that for j = 0 and N >= 2, we have:
F_N = SUM[k=0 to 0; C(0,k)F_{N2*0+k}] = F_N and 1 <= N/2 so now all we
need is the inductive step.
Suppose it is true that:
[2] F_N = SUM[k=0 to j; C(j,k)F_{N2j+k}] for j = J <= N/2  1
we need to show that:
[3] F_N = SUM[k=0 to j; C(j,k)F_{N2j+k}] for j = J+1
From the sum in [2], we will break down each F_i into F_{i1} + F_{i2}.
In [2], i will range from N2J to NJ as k runs from 0 to J. After
breaking down the terms, our highest term will be NJ1 and our lowest
will be N2J2. So in our new sum, our index p will run from N2J2 to
NJ1 as k runs from 0 to J+1. That is, p = N2J+k or k = pN+2J. We
will consider 3 cases:
Case 1: p = N2J2
Case 2: p = NJ1
Case 3: N2J2 < p < NJ1
Case 1: p = N2J2 (that is, our least term in our new sum... we know
that we want the coefficient for this Fibonacci to be 1)
There is only one term in [2] that has F_{N2J2} in its decomposition
and that is: F_{N2J} = F_{N2J1} + F_{N2J2}. The coefficient for
F{N2J} is C(J,0) = 1 and thus the coefficient for F_{N2J2} will also
be 1.
Case 2: p = NJ1 (this establishes our highest term in our new sum)
Again there is only one term in [2] that has F_{NJ1} in its
decomposition and that is: F_{NJ} = F_{NJ1} + F{NJ2}. The
coefficient for F{NJ} is C(J,J) = 1 and thus the coefficient for
F_{NJ1) will also be 1.
Case 3: N2J2 < p < NJ1 (this establishes all of our other terms in
our new sum)
For each p, there are exactly two terms in [2] that has F_p in its
decomposition and those are F_{p+1} = F_p + F_{p1} and F_{p+2} =
F_{p+1} + F_p. In [2], N2J+k = p+1 when k = p+1N+2J so the
coefficient for F_{p+1} is C(J,p+1N+2J) and similarly the coefficient
for F_{p+2} is C(J,p+2N+2J).
So the coefficient for F_p in the decomposition will be the sum of the
coefficients for F_{p+1} and F_{p+2} in [2].
Recall that:
[4] C(a,b)+C(a,b+1)=C(a+1,b+1)
Letting a = J and p+1N+2J = b, the coefficient for F_p in the
decomposition is: C(J+1,p+2N+2J)
So the sum in our decomposition will be:
SUM[p=N2J2 to NJ1; C(J+1,p+2N+2J)F_p]
Letting k = pN+2J+2 [and thus p = N2(J+1)+k], we get:
SUM[k=0 to J+1; C(J+1,k)F_{N2(J+1)+k}] which completes our inductive
step and thus our proof.
 Matt 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Mon Oct 24, 2005 5:47 am Post subject:
Re: Binomial Coefficients and Fibonacci



Doug Mitchell wrote:
Quote:  I think to be rigorously prove the following relationship:
SUM[k=0 to n; C(n,k) F_k] = F_{2n} where F_k is the kth Fibonacci term
I would need to use....induction?
Well I see that it holds for n=1, or 2
And I think the 'induction hypothesis' would be SUM [k=0 to n; C(n.k)
F_k]=F_{2n}?
And to complete the proof it now needs to be shown that the relationship
hold in the "n+1" case?
i.e. SUM [k=0 to n+1; C(n+1.k) F_k]=F_{2(n+1)} ??
I dont see how I can use the induction hypothesis to prove this "n+1" case.

C(n+1,k) = C(n,k1) + C(n,k), but then you'd also need to know what
SUM [k=0 to n; C(n,k1) F_k].
 Christopher Heckman 

Back to top 


Doug Mitchell science forum beginner
Joined: 23 Oct 2005
Posts: 1

Posted: Sun Oct 23, 2005 10:33 am Post subject:
Binomial Coefficients and Fibonacci



I think to be rigorously prove the following relationship:
SUM[k=0 to n; C(n,k) F_k] = F_{2n} where F_k is the kth Fibonacci term
I would need to use....induction?
Well I see that it holds for n=1, or 2
And I think the 'induction hypothesis' would be SUM [k=0 to n; C(n.k)
F_k]=F_{2n}?
And to complete the proof it now needs to be shown that the relationship
hold in the "n+1" case?
i.e. SUM [k=0 to n+1; C(n+1.k) F_k]=F_{2(n+1)} ??
I dont see how I can use the induction hypothesis to prove this "n+1" case. 

Back to top 


Google


Back to top 



The time now is Tue Apr 23, 2019 11:53 am  All times are GMT

