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:
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.
Lets prove that this summation
have the inicial conditions g(1)=g(2)=1 and the recurrence relation
so it is the fibonacci sequence F(n)
so the initial conditions are ok
lets show that it is
Thank you both for your excellent methods. This proof is far more clear now. :)