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?