 Forum index » Science and Technology » Math » Combinatorics
Author Message
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. 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,k-1) + C(n,k), but then you'd also need to know what

SUM [k=0 to n; C(n,k-1) F_k].

--- Christopher Heckman 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:
 F_N = SUM[k=0 to j; C(j,k)F_{N-2j+k}]
for j <= N/2
Once we succeed in proving , 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 ? For this, we will use induction on j.

For any N, if F_N = SUM[k=0 to j; C(j,k)F_{N-2j+k}] for j+1 <= N/2 then
F_N = SUM[k=0 to j+1; C(j+1,k)F_{N-2(j+1)+k}]

First, observe that when j+1 <= N/2, N-2(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_{N-2*0+k}] = F_N and 1 <= N/2 so now all we
need is the inductive step.

Suppose it is true that:
 F_N = SUM[k=0 to j; C(j,k)F_{N-2j+k}] for j = J <= N/2 - 1

we need to show that:
 F_N = SUM[k=0 to j; C(j,k)F_{N-2j+k}] for j = J+1

From the sum in , we will break down each F_i into F_{i-1} + F_{i-2}.
In , i will range from N-2J to N-J as k runs from 0 to J. After
breaking down the terms, our highest term will be N-J-1 and our lowest
will be N-2J-2. So in our new sum, our index p will run from N-2J-2 to
N-J-1 as k runs from 0 to J+1. That is, p = N-2J+k or k = p-N+2J. We
will consider 3 cases:
Case 1: p = N-2J-2
Case 2: p = N-J-1
Case 3: N-2J-2 < p < N-J-1

Case 1: p = N-2J-2 (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  that has F_{N-2J-2} in its decomposition
and that is: F_{N-2J} = F_{N-2J-1} + F_{N-2J-2}. The coefficient for
F{N-2J} is C(J,0) = 1 and thus the coefficient for F_{N-2J-2} will also
be 1.
Case 2: p = N-J-1 (this establishes our highest term in our new sum)
Again there is only one term in  that has F_{N-J-1} in its
decomposition and that is: F_{N-J} = F_{N-J-1} + F{N-J-2}. The
coefficient for F{N-J} is C(J,J) = 1 and thus the coefficient for
F_{N-J-1) will also be 1.
Case 3: N-2J-2 < p < N-J-1 (this establishes all of our other terms in
our new sum)
For each p, there are exactly two terms in  that has F_p in its
decomposition and those are F_{p+1} = F_p + F_{p-1} and F_{p+2} =
F_{p+1} + F_p. In , N-2J+k = p+1 when k = p+1-N+2J so the
coefficient for F_{p+1} is C(J,p+1-N+2J) and similarly the coefficient
for F_{p+2} is C(J,p+2-N+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 .

Recall that:
 C(a,b)+C(a,b+1)=C(a+1,b+1)

Letting a = J and p+1-N+2J = b, the coefficient for F_p in the
decomposition is: C(J+1,p+2-N+2J)

So the sum in our decomposition will be:
SUM[p=N-2J-2 to N-J-1; C(J+1,p+2-N+2J)F_p]

Letting k = p-N+2J+2 [and thus p = N-2(J+1)+k], we get:
SUM[k=0 to J+1; C(J+1,k)F_{N-2(J+1)+k}] which completes our inductive
step and thus our proof.

- Matt  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 The time now is Fri Mar 22, 2019 4:38 am | All times are GMT Forum index » Science and Technology » Math » Combinatorics
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Functional PDE with constant coefficients stefan1 Math 0 Mon Jun 26, 2006 5:55 pm Parity of Sum of Binomial Coefficients. googleposter226@yahoo.com Math 4 Wed Jun 21, 2006 4:29 pm Binomial and hypergeometric distributions Eli Luong Math 3 Thu Jun 15, 2006 2:49 am Binomial Distribution--> Poisson Distribution?? when??? group.fbi@gmail.com Probability 1 Sun Jun 11, 2006 2:31 pm binomial problem? Computers Guru Math 1 Tue Jun 06, 2006 7:43 pm