FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
Binomial Coefficients and Fibonacci
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
Author Message
Doug Mitchell
science forum beginner


Joined: 23 Oct 2005
Posts: 1

PostPosted: Sun Oct 23, 2005 10:33 am    Post subject: Binomial Coefficients and Fibonacci Reply with 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.
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Mon Oct 24, 2005 5:47 am    Post subject: Re: Binomial Coefficients and Fibonacci Reply with quote

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
Back to top
Matthew Roozee
science forum beginner


Joined: 22 Oct 2005
Posts: 7

PostPosted: Mon Oct 24, 2005 7:52 am    Post subject: Re: Binomial Coefficients and Fibonacci Reply with quote

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_{N-2j+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_{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:
[2] 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:
[3] F_N = SUM[k=0 to j; C(j,k)F_{N-2j+k}] for j = J+1

From the sum in [2], we will break down each F_i into F_{i-1} + F_{i-2}.
In [2], 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 [2] 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 [2] 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 [2] 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 [2], 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 [2].

Recall that:
[4] 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
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
The time now is Thu Nov 23, 2017 10:58 am | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0198s ][ Queries: 16 (0.0032s) ][ GZIP on - Debug on ]