Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

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,

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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search