Pascal's Triangle and Fibonacci Formula

Date: 02/23/2002 at 18:22:22
From: Yael
Subject: Proof of a theory 

The diagonals of Pascal's triangle give the Fibonacci numbers. As the 
numbers are also binomial coefficients, I wrote down some equations 
of the diagonals:

(0,0) = 1
(1,0) = 1
(2,0)+(1,1) = 2
(3,0)+(2,1) = 3
(4,0)+(3,1)+(2,2) = 5
(5,0)+(4,1)+(3,2)=1+4+3 = 8
(6,0)+(5,1)+(4,2)+(3,3) = 1+5+6+1 = 13
(7,0)+(6,1)+(5,2)+(4,3) = 1+6+10+4 = 21
(8,0)+(7,1)+(6,2)+(5,3)+(4,4) = 1+7+15+10+1 = 54

so I tried to create a formula 

   fib(n) = sum_{k=0}^{n/2} {n-1-k,k} 

I would like to know if this formula is correct. 

I looked this problem up on the Web and on R. Knott's site and found 
two unrelated formulas:

   fib(n) = sum_{k=0}^{n-1} {n-k-1,k}
   fib(n) = sum_{k=1}^{n} {n-k,k-1}

I plugged in numbers and it didn't work. Maybe I'm wrong. I don't 
know. 

i then found a formula of lucas, 1876

   F(n+1) = sum_{i=0}^{n/2} {n-i,i}   n>=0

I think this is the same as mine, no?

My thing to do was to prove why the diagonals of Pascal's triangle 
are the Fibonacci numbers by myself. Is what I did enough for 'my 
proof'? 

Thank you very much for taking your time. I think you do great jobs 
from what I've seen of the archives. Again, thank you for taking a 
look at 'my problem', if it is one!

Yael

Date: 03/04/2002 at 07:05:54
From: Doctor Floor
Subject: Re: Proof of a theory 

Hi, Yael,

Thanks for your question.

The way to formulate the theorem of connecting the Fibonacci numbers 
and Pascal's theorem you attribute to Lucas is correct, and I think 
useful as well. The only thing is that the n/2 would better be 
floor(n/2), where floor(p) is the largest integer smaller than p.

The formula on Ron Knott's pages uses the extra assumption that if 
n<k then (n,k)=0; with that assumption his formulae are correct as 
well.

For the proof I think it would be good to use mathematical induction. 
You show that f(1) = f(2)=1 with your formula, and that 
f(n+2) = f(n+1)+f(n). Perhaps the easiest way to prove this last step 
is to distinguish even and odd n. It think it is a good idea to use 
the formula:

 (n,r) + (n,r+1) = (n+1,r+1)

I hope this puts you on track.

If you have more questions, just write back.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/   

Date: 03/06/2002 at 18:52:20
From: Yael
Subject: Proof of a theory 

Dear Dr. Floor, 

As you say: f(n+2) = f(n+1)+f(n)

So, sum_{k=0}^{floor((n+2)/2)} {n+1-k,k} =
    sum_{k=0}^{floor((n+1)/2)} {n-k,k} + sum_{k=0}^{floor(n/2)} 
     {n-1-k,k}(*)
[with floor meaning in your sense largest integer smaller than p]

I have tried to work on this for an hour, but can't seem to get to 
something useful.

I know you said it is a good idea to use the formula 
 (n,r) + (n,r+1) = (n+1,r+1)
but I didn't get that at all...sorry... I mean if you plug in numbers, 
I saw all right that this formula is true, but I didn't get the 
connection to the other formula we had (the sum one)...

Please could you help me with solving this -->(*). 
You said one should separate it into even and odd, so could you at 
least do it for even n's, please?

Thank you so much for taking time to help me out.

Yael

Date: 03/07/2002 at 03:08:27
From: Doctor Floor
Subject: Re: proof of a theory
Hi, Yael,

Thanks for your reaction.

First, for the formula (n,r) + (n,r+1) = (n+1,r+1) [**], where we 
still assume that (n,r) = n C r, see the Dr. Math archives at

  Binomial Theorem by Induction
  http://mathforum.org/dr.math/problems/turner.7.14.96.html   

This is also just the addition rule for Pascal's triangle (each entry 
is the sum of the two entries above it).


Then, you gave the formula to prove 
sum_{k=0}^{floor((n+2)/2)} (n+1-k,k) =
sum_{k=0}^{floor((n+1)/2)} (n-k,k) + sum_{k=0}^{floor(n/2)} (n-1-k,k).

This needs a little adjustment according to the formula you gave, and 
it seems correct,

 fib(n) = sum_{k=0}^{floor((n-1)/2)} {n-1-k,k}.

Your formula (*) should thus be

sum_{k=0}^{floor((n+1)/2)} (n+1-k,k) =
sum_{k=0}^{floor(n/2)} (n-k,k) + sum_{k=0}^{floor((n-1)/2)} (n-1-k,k).

Using formula [**] we will prove this identity.

Case 1, n = even:

When n is even, then floor((n+1)/2) = floor(n/2) = n/2 and 
floor((n-1)/2) = n/2-1. Hence we have

sum_{k=0}^{floor(n/2)} (n-k,k) + sum_{k=0}^{floor((n-1)/2} (n-1-k,k) =
sum_{k=0}^{n/2} (n-k,k) + sum_{k=0}^{n/2-1} (n-1-k,k) =

  <substitute k' = k+1 in the second sum>

sum_{k=0}^{n/2} (n-k,k) + sum_{k'=1}^{n/2} (n-k',k'-1) =
(n,0) + sum_{k=1}^{n/2} (n-k,k) + sum_{k'=1}^{n/2} (n-k',k'-1) =
1 + sum_{k=1}^{n/2} [(n-k,k) + (n-k,k-1)] =

  <use formula [**]>

(n+1,0) + sum_{k=1}^{n/2} (n-k+1,k) = sum_{k=0}^{n/2} (n-k+1,k)

as desired.

Case 2, n = odd:

When n is odd, then floor((n-1)/2) = floor(n/2) = (n-1)/2 and 
floor((n+1)/2) = (n+1)/2. Hence we have

sum_{k=0}^{floor(n/2)} (n-k,k) + sum_{k=0}^{floor((n-1)/2} (n-1-k,k) =
sum_{k=0}^{(n-1)/2} (n-k,k) + sum_{k=0}^{(n-1)/2-1} (n-1-k,k) =

  <substitute k' = k+1 in the second sum>

sum_{k=0}^{(n-1)/2} (n-k,k) + sum_{k'=1}^{(n+1)/2} (n-k',k'-1) =
(n,0) + sum_{k=1}^{(n-1)/2} (n-k,k) + ((n-1)/2,(n-1)/2) 
      + sum_{k'=1}^{(n-1)/2} (n-k',k'-1) =
2 + sum_{k=1}^{(n-1)/2} [(n-k,k) + (n-k,k-1)] =

  <use formula [**]>

(n+1,0) +((n+1)/2,(n+1)/2) + sum_{k=1}^{(n-1)/2} (n-k+1,k) =
sum_{k=0}^{(n+1)/2} (n-k+1,k)

as desired.

I hope this helped you out.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/