4
$\begingroup$

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!

$\endgroup$
1

1 Answer 1

8
$\begingroup$

$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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.