# Estimating when does a certain binomial sum exceed an upper bound

Given a fixed integer $n > 0$ and $0 \le m \le n$ let us define the numbers

$$f_{n,m} = \sum_{i=\lfloor m/2 \rfloor}^m {n-2i \choose n - m -i}{i+1 \choose m - i +1}.$$

For example $f_{n,0} = 1,f_{n,1} =2$ and $f_{n,2} = n+1.$ What I am interested in is the following inequality

$$\sum_{m=0}^k (n-m+1)f_{n,m} \geq f_{n+2} \ge \frac{(\frac{1+\sqrt{5}}{2})^{n+1}}{\sqrt{5}} \; \; \; (1),$$

where $f_n$ is the $n$th Fibonacci number.

More specifically, I would like a lower bound for the least number $k$ such that the inequality is satisfied.

For example if $k = 3$ then the sum on the left is just $(n+1)^2-5$ which is clearly smaller than $f_{n+2}$ (for large enough $n$'s.)

Now the only way that I know for attacking this is to estimate $f_{n,m}$ by using the well known bound ${n \choose k} \geq (\frac{n}{k})^k$ and use the integral inequality for summations. Unfortunately Mathematica (and hence I) cannot compute the definite integral of the obtained function and hence I am wondering:

Is there some other way to analyze this inequality? What would be a good bound for $k$ such that $(1)$ holds? Can the theory of generating functions help us?

-
Have you tried looking at the largest term (or two largest) in the sum for fn,m? That should help with a good bound on k. – The Masked Avenger May 13 '14 at 17:26
Can you check your example for k=3? I am not getting n+3 for the sum of f's. – The Masked Avenger May 13 '14 at 17:31
err you're right I forgot to multiply with the respective coefficients of $f_{n,m}$ hopefully its ok now. – Jernej May 13 '14 at 17:33
Also, it looks to me like k will be Omega(n/log n) for the inequality to hold. – The Masked Avenger May 13 '14 at 17:38
@TheMaskedAvenger Could you explain how you got to this conclusion? – Jernej May 13 '14 at 18:54