Pascal-Fibonacci Proof

• Oct 3rd 2009, 04:13 PM
Tulki
Pascal-Fibonacci Proof
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.
• Oct 4th 2009, 12:15 AM
NonCommAlg
Quote:

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$
• Oct 4th 2009, 02:45 AM
Renji Rodrigo
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)$
• Oct 4th 2009, 12:55 PM
Tulki
Thanks!
Thank you both for your excellent methods. This proof is far more clear now. :)