Fibonacci numbers written as sums of binomial coefficients

Question

So I came across this formula of Fibonacci numbers as a binomial sum [1] [2]

$$ F_n = \sum_{k \mathop = 0}^{\lfloor {\frac {n - 1} 2} \rfloor} \dbinom {n - k - 1} k $$

I'm not really sure that this formula actually valid, I've computed some of the first terms and they don't look very much like Fibonacci numbers to me.

Maybe the identity is wrong, but several places have it stated in the same way. Does anyone know more about this identity? Thanks

#!/usr/bin/python3
from math import factorial, floor

def c(n,k):
    return factorial(n)/(factorial(k)*factorial(n-k))

def f(n):
    s=0
    for k in range(floor((n-1)/2)):
        s += int(c(n-k-1,k))
    return s

for n in range(1,6):
    # computing F(n)
    print(f(n))

And the output is

0
0
1
1
4

[1] https://proofwiki.org/wiki/Fibonacci_Number_as_Sum_of_Binomial_Coefficients

[2] https://math.stackexchange.com/a/169893/68328

Answer 1

This is a programming problem. In python, the loop

for k in range(n):

will execute its statements inside for $k=0,1,...,n-1$, so that the computed sums contain one term less than necessary.