Another computationally useless sum for Fibonacci numbers
 

The well-known geometric series expansion 1/(1 - x - x^2) = 1 + (x + x^2) + (x + x^2)^2 + (x + x^2)^3 + ... =

1 + F[sub]2[/sub]x + F[sub]3[/sub]x^2 + F[sub]4[/sub]x^3 + F[sub]5[/sub]x^4 + ...

(valid when |x + x^2| < 1) gives the equally well-known identity

SUM, k = 0, floor(n/2), binomial(n-k,k) = F[sub]n[/sub].

Calling the series expansion G(x), the identity

(1 - x - x^2)*G(x) = 1

gives the recursion for the Fibonacci numbers; verifying the coefficients for 1 and x then allows a proof by induction that the coefficients are as stated.

Another, less well-known identity relating the n-th Fibonacci number to binomial coefficients, all in the n-th row, is as follows.
[code] Let r = floor((n-1)/2). Then

SUM, k == r (mod 5) binomial(n,k) - SUM, k == r-1 (mod 5) binomial (n,k) = F[sub]n[/sub].[/code]

I don't recall even whether I ever worked out a proper proof. I note that we can express the sum of the binomial coefficients binomial(n, j) for j in any given congruence class (mod 5) by taking a simple linear combination of

(1 + w)^n, w = exp(2*k*I*Pi/5), k = 0 to 5.

In each case, the main term will be 2^n/5; this cancels out when you subtract the sum of the binomial coefficients in one residue class from the sum of those in another.

As a puzzle challenge, I invite the denizens of this Forum to devise a proof of the above identity.

Let b(n, k) be the sum of binomials (n, i) with i equaling k mod 5. Then easily b(n+1, k) = b(n, k) + b(n, k-1), and from this b(n+2, k) = b(n, k) + 2b(n, k-1) + b(n, k-2). When n increases by 2, the two values of k we want to calculate b(n, k) for increase by 1. Define c from b to compensate for this with c(n, k)=b(n, k-n/2), so that if c(n, k) = b(n, m) for some m, then c(n+2, k) = b(n+2, m+1). Now c(n+2, k) = 2*c(n, k) + c(n, k-1) + c(n, k+1), and the values of k we subtract from each other are fixed.

I'll only handle the even n case explicitly here.
The values of c(2*n, k) for first few n and k from 0 to 4 are:

[1, 0, 0, 0, 0]; n = 0
[2, 1, 0, 0, 1]
[6, 4, 1, 1, 4]
[20, 15, 7, 7, 15]; n = 3, 2n=6
The fibonacci number is last minus second-to-last numbers on each row, or equally second minus third.

Generally there are only only three distinct values (-k equals k). Marking these by a, b, c (for k=0, 1, 2), we can rewrite the calculation from one row to the next as
a, b, c = 2a+2b, a+2b+c, b+3c
Since only differences matter, we can subtract b+3c from each, giving
a, b, c = 2a+b-3c, a+b-2c, 0
and since now c is always 0, this can be further simplified to
a, b, c = 2a+b, a+b, 0
But "a, b = 2a+b, a+b" is just the formula for advancing a pair of two consecutive Fibonacci numbers by two steps, so the claim can be proven by induction.