How to show this inequality involving generalized Fibonacci sequence?

Question

Define recursively, $$f(n,k) = \sum_{i=1}^{k}f(n-i,k)$$ with initial conditions $f(n,k)=0$ for $n<0$ and $f(0,k)=1.$ For starters observe that $$\lim_{n\to \infty}\frac{f(n+1,k)}{f(n,k)}=\phi(k)$$ where $\phi(k)>0$ is the positive root of the polynomial $$g_k(x) = x^{k}-\sum_{0\leq l< k}x.$$ Then I observed that, $$\lim_{k\to \infty} \phi(k)=2.$$ I intend to prove this fact by showing that $$2(1-2^{-k})<\phi(k)<2.$$ I understand why $\phi(k)<2$ since $g_k(2)=1.$ But I am not sure why $$2(1-2^{-k})<\phi(k)$$ holds. I have shown that $$\phi(k)<\phi(k+1)$$ perhaps this helps in proving this inequality. I don't know. Any ideas to prove the inequality will be much appreciated.

Answer 1

The strict lower bound doesn’t hold at $k=1$. Indeed, $g_1(x)=x-1$ so $\phi(1)=1=2(1-2^{-1})$. Here equality holds.

Let us thus suppose $k \geq 2$. Then $g_k(1)=1-k \neq 0$ so $\phi(k) \neq 1$. Now $\phi(k)$ is a root (other than $1$) of $p(x)=(1-x)g_k(x)=x^k(1-x)-(1-x^k)=x^k(2-x)-1$. We have $p’(x)=x^{k-1}(2k-(k+1)x)$. Thus $p(x)$ is increasing on $[0, \frac{2k}{k+1}]$ and decreasing on $[\frac{2k}{k+1},\infty]$. We have $p(1)=0, p(2)=-1$.

Remark: If we just wanted to prove the weaker statement $\lim_{k\to \infty} \phi(k)=2$, note that we clearly have $\phi(k) \in (\frac{2k}{k+1},2)$ so we are done. The stronger lower bound is proved below.

Note $2^k=(1+1)^k \geq 1+k$ using Bernoulli’s inequality/binomial expansion. Thus $2(1-2^{-k}) \geq 2(1-\frac{1}{k+1})=\frac{2k}{k+1}$. Finally $$ \begin{align} p(2(1-2^{-k})) &=(2(1-2^{-k})^k(2(2^{-k}))-1 \\ &=2(1-2^{-k})^k-1 \\ & >2(1-k2^{-k})-1 \\ &=1-\frac{k}{2^{k-1}} \\ & \geq 0 \\ \end{align}$$ where we have used the strict version of Bernoulli’s inequality for the first inequality, and Bernoulli again/binomial expansion on $2^{k-1}$ for the second inequality.

Thus $p(x)<0=p(1)$ on $[0,1)$, $0=p(1)<p(x)$ on $(1,\frac{2k}{k+1}]$, $p(x) \geq p(2(1-2^{-k}))>0$ on $[\frac{2k}{k+1},2(1-2^{-k})]$ and $p(x) \leq p(2)<0$ on $[2,\infty)$. Thus we conclude $\phi(k) \in (2(1-2^{-k}), 2)$.

Remark: In fact, we easily see $p(2(1-2^{-(k+1)}))=(2(1-2^{-(k+1)}))^k 2^{-k}-1=(1-2^{-(k+1)})^k-1<0$, so we may conclude $\phi(k) \in ((2(1-2^{-k}), 2(1-2^{-(k+1)}))$.