Pascal-Fibonacci Proof

**Tulki** · October 3rd 2009, 04:13 PM

Every once in awhile our Professor asks us a challenge question for "fun". Well, I'm totally stumped this time.

He's asked us if we can prove the Fibonacci sequence. So far, we've only learned Set Theory, Combinatorics, and the beginning of propositional logic (just truth tables, really).

He gave us this to prove:
Fibonacci Sequence

f(n+1) = C(n,0) + C(n-1,1) + ... + C(n-k,k)

n >= 0 and k = floor(n/2) meaning k is (n/2) rounded down.

f(0) and f(1) are seeding values 0 and 1, respectively.

He then hinted that we need to prove Pascal's pattern first, in order to prove the Fibonacci Sequence.
He gave us Pascal's:

C(n,k) = C(n-1,k) + C(n-1,k-1)

n,k are integers, 1<= k < (n-1)

Now, I'm able to prove Pascal algebraically, but I'm not sure how that helps to solve the overall question. Is there a way I can make use of the binomial theorem here? If anyone can help me get started on this, I'd be extremely grateful.

**NonCommAlg** · October 4th 2009, 12:15 AM

Originally Posted by Tulki

Every once in awhile our Professor asks us a challenge question for "fun". Well, I'm totally stumped this time.

He's asked us if we can prove the Fibonacci sequence. So far, we've only learned Set Theory, Combinatorics, and the beginning of propositional logic (just truth tables, really).

He gave us this to prove:
Fibonacci Sequence

f(n+1) = C(n,0) + C(n-1,1) + ... + C(n-k,k)

n >= 0 and k = floor(n/2) meaning k is (n/2) rounded down.

f(0) and f(1) are seeding values 0 and 1, respectively.

He then hinted that we need to prove Pascal's pattern first, in order to prove the Fibonacci Sequence.
He gave us Pascal's:

C(n,k) = C(n-1,k) + C(n-1,k-1)

n,k are integers, 1<= k < (n-1)

Now, I'm able to prove Pascal algebraically, but I'm not sure how that helps to solve the overall question. Is there a way I can make use of the binomial theorem here? If anyone can help me get started on this, I'd be extremely grateful.

prove it by induction over $n$ . it's clear for n = 0, 1. let $n \geq 2$ and suppose that the identity holds for $f(m+1)$ with $m < n.$ also, for any integer $\ell$ define $g(\ell)=\lfloor \ell/2 \rfloor.$ then:

$f(n+1)=f(n)+f(n-1)=\sum_{i=0}^{g(n-1)} \binom{n-1-i}{i}+\sum_{j=0}^{g(n-2)} \binom{n-2-j}{j}$

$=\sum_{i=0}^{g(n-1)} \binom{n-1-i}{i}+\sum_{i=1}^{g(n-2)+1} \binom{n-1-i}{i-1}$

$=\sum_{i=0}^{g(n-1)} \binom{n-1-i}{i}+ \sum_{i=1}^{g(n)} \binom{n-1-i}{i-1} \ \ \ \ \ \ \ \ \ \ \ (1)$

now we have $g(n-1)=\begin{cases} g(n) & \text{if n is odd} \\ g(n) - 1 & \text{if n is even} \end{cases}.$ so using $(1)$ and Pascal's identity we have:

case 1 if $n$ is odd, then:

$f(n+1)=1 + \sum_{i=1}^{g(n)} \left[\binom{n-1-i}{i}+ \binom{n-1-i}{i-1} \right]= 1 + \sum_{i=1}^{g(n)}\binom{n-i}{i}=\sum_{i=0}^{g(n)} \binom{n-i}{i}.$

case 2 if $n$ is even, then:

$f(n+1)=1 + \sum_{i=1}^{g(n)-1} \left[\binom{n-1-i}{i}+ \binom{n-1-i}{i-1} \right] + \binom{n-1-g(n)}{g(n)-1}$

$=1+ \sum_{i=1}^{g(n)-1} \binom{n-i}{i} + \binom{n-g(n)}{g(n)}=\sum_{i=0}^{g(n)} \binom{n-i}{i}. \ \ \ \Box$

**Renji Rodrigo** · October 4th 2009, 02:45 AM

Other solution
Lets prove that this summation
$g(n+1)=\sum^{n}_{k=0}{n-k \choose k}$
have the inicial conditions g(1)=g(2)=1 and the recurrence relation
$g(n+3)=g(n+2)+g(n+1)$
so it is the fibonacci sequence F(n)

We have
$\sum^{0}_{k=0}{0-k \choose k}={0 \choose 0}=1=F(1)=G(1)$
$\sum^{1}_{k=0}{1-k \choose k}={1 \choose 0}+{0 \choose 1}=1=F(2)=G(2)$
so the initial conditions are ok

$g(n+2)=\sum^{n+1}_{k=0}{n+1-k \choose k}=\sum^{n}_{k=0}{n+1-k \choose k} +{0 \choose n+1}=\sum^{n}_{k=0}{n+1-k \choose k}$

$g(n+2)+g(n+1)=\sum^{n}_{k=0}{n+1-k \choose k}+{n-k \choose k}$
lets show that it is $g(n+3)$

$g(n+3)=\sum^{n+2}_{k=0}{n+2-k \choose k}= \sum^{n+1}_{k=0}{n+2-k \choose k} + {0 \choose n+2}= \sum^{n+1}_{k=0}{n+2-k \choose k}=$

$=\sum^{n+1}_{k=0}{n+1-k \choose k} +\sum^{n+1}_{k=0}{n+1-k \choose k-1}=$
$\sum^{n}_{k=0}{n+1-k \choose k}+{0 \choose n+1} +\sum^{n+1}_{k=1}{n+1-k \choose k-1}=$
$=\sum^{n}_{k=0}{n+1-k \choose k} +\sum^{n}_{k=0}{n-k \choose k}=g(n+2)+g(n+1)$

**Tulki** · October 4th 2009, 12:55 PM

Thank you both for your excellent methods. This proof is far more clear now.

Thread: Pascal-Fibonacci Proof

LinkBack

Thread Tools

Display

Pascal-Fibonacci Proof

Thanks!

Similar Math Help Forum Discussions

sum of (n+1)th row pascal triangle proof

Fibonacci Proof

Need help on Fibonacci proof

Another Fibonacci Proof

Fibonacci numbers from Pascal's triangle

Search Tags