An inequality involving $k$-generalized Fibonacci numbers

Question

I have worked on a Diophantine equation by using transcendental and reduction methods given by Baker and Davenport. However, to solve completely the equation I have one complicated case and I proved that for this case it is enough to prove the following inequality $$ F_{2m-2}^{(k)}<(F_m^{(k)})^2+1, $$ for all $m\geq 1$ and $k\geq 3$ (or $m>k+1$).

Here, $(F_m^{(k)})_{m\geq -(k-2)}$ is defined by the recurrence $$ F_m^{(k)}=F_{m-1}^{(k)}+F_{m-2}^{(k)}+\cdots + F_{m-k}^{(k)}, $$ with initial values $0,0,\ldots, 0,1=F_1^{(k)}$ ($k-1$ zeroes).

Any suggestion could be very helpful. Thanks in advance!

Answer 1

$F_{\ell+1}$ is just the number of ways to tile an interval of length $\ell$ by tiles of lengths up to $k$. Now take the interval of length $2m-3$ and look at what happens at the mark $m-2$. You may have it as a boundary point, which gives you $F_{m-1}F_m$ configurations or you may have it splitting one of the intervals into two subintervals with the left one of length $a\in\{1,\dots,k-1\}$ , which gives you at most $F_{m-1-a}F_{m}$ configurations. Thus, the total number of configurations is at most $\left[\sum_{a=0}^{k-1}F_{m-1-a}\right]F_m=F_m^2$, so, indeed, $F_{2m-2}\le F_m^2$.