show that $\frac{1}{F_{1}}+\frac{2}{F_{2}}+\cdots+\frac{n}{F_{n}}<13$

Question

Let $F_{n}$ is Fibonacci number,ie.($F_{n}=F_{n-1}+F_{n-2},F_{1}=F_{2}=1$)

show that $$\dfrac{1}{F_{1}}+\dfrac{2}{F_{2}}+\cdots+\dfrac{n}{F_{n}}<13$$

if we use Closed-form expression $$F_{n}=\dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right)$$ $$\dfrac{n}{F_{n}}=\dfrac{\sqrt{5}n}{\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right)}$$

Well and now I'm stuck and don't know how to proceed

Answer 1

Let $\phi=\frac{1+\sqrt{5}}{2}$. Then $\phi^2=\phi+1$.

By induction, we have $F_n > \phi^{n-2}$ for all $n\ge 1$, and so $$ \sum_{n=1}^{N} \frac{n}{F_n} < \sum_{n=1}^{\infty} \frac{n}{F_n} < \sum_{n=1}^{\infty} \frac{n}{\phi^{n-2}} = \sum_{n=1}^{\infty} \frac{n\phi^2}{\phi^{n}} = \phi^2 \sum_{n=0}^{\infty} \frac{n}{\phi^{n}} = \frac{\phi^3}{(1-\phi)^2} = \frac{1+2\phi}{2-\phi} < 13 $$ because $\phi< \dfrac53$.

I've used that $\phi^2=\phi+1$ and so $\phi^3=\phi\phi^2=\phi^2+\phi=2\phi+1$.

(The value of the last fraction above is $\approx 11.09$. It is the same as Simon's bound.)

Answer 2

Here's one rough approach which works for $n$ sufficiently large. The idea is that for large $n$, we have that $$ F_n \approx \phi^n/\sqrt{5} $$ since the conjugate root is less than one, and so it tends to zero.

So consider now the generating function $$ G(q) = \sum_{n=0}^\infty \frac{q^n}{F_n} $$ We note that your sum approaches $\big(q\frac{d}{dq}G(q)\big)_{q=1}$ and so we just need to evaluate that expression. Using the approximating above, we see that $$ G(q) \approx \sum_{n=0}^\infty \sqrt{5}\frac{q^n}{\phi^n} = \sqrt{5}\frac{\phi}{\phi - q} $$ and so taking the derivative we get $$ q\frac{d}{dq}G(q) \approx \frac{\sqrt{5}\phi}{(\phi - 1)^2} $$ which, when evaluated at $q = 1$ yields $9.4721\ldots < 13$

There are obviously some details that would probably need to be filled in here (how good are the approximations?), but this could give you a rough start.

Edit

Here is a full proof. We first define $G_n(q) = \sum_{k=0}^n \frac{nq^n}{F_n}$ and $G(q) = \sum_{k=0}^\infty \frac{nq^n}{F_n}$. Clearly, $G_n(q) < G(q)$ (if $q > 0$). So our goal is to bound $G(1)$. Define $D = q\frac{d}{dq}$. We have: $$ \begin{align} G(q) &= D\sum_{k=0}^\infty \frac{q^n}{F_n} \\ &= D\sum_{k=0}^\infty \frac{\sqrt{5}q^n}{\phi^n - \phi'^n} \\ &= D\sum_{k=0}^\infty \frac{\sqrt{5}q^n}{\phi^n\big(1 - (\phi'/\phi)^n\big)} \end{align} $$ The point now is that we always have that $$ \frac{1}{1 - (\phi'/\phi)^n} < \frac{1}{1 - (\phi'/\phi)^2} $$ since this is equivalent to $(\phi'/\phi)^n < (\phi'/\phi)^2$ which is vacuously true if $n$ is odd (the LHS is negative) and true if $n$ is even since $|\phi'/\phi| < 1$. Thus $$ G(q) = D\sum_{k=0}^\infty \frac{\sqrt{5}q^n}{\phi^n\big(1 - (\phi'/\phi)^n\big)} < \frac{\sqrt{5}}{1 - (\phi'/\phi)^2}D\sum_{k=0}^\infty \frac{q^n}{\phi^n} $$ from which we have (looking at the previous argument) that $$ G_n(1) < G(1) < \frac{\sqrt{5}}{1 - (\phi'/\phi)^2}\frac{\phi}{(\phi - 1)^2} \approx 11.08 < 13 $$

Answer 3

Lemma $$F_{n}\ge\dfrac{n(n+1)(n+2)}{42},n\ge 5$$ proof:use induction, since $$\dfrac{1}{42}[k(k+1)(k+2)+(k+1)(k+2)(k+3)]=\dfrac{1}{42}(k+1)(k+2)(2k+3)$$ and $$(k+1)(2k+3)\ge (k+3)(k+4)$$

so $$\dfrac{n}{F_{n}}\le \dfrac{42}{(n+1)(n+2)}$$ so $$\sum_{k=1}^{n}\dfrac{k}{F_{k}}\le 1+2+\dfrac{3}{2}+\dfrac{4}{3}+42\left(\dfrac{1}{6}-\dfrac{1}{n+2}\right)<13$$

Answer 4

$q=0.624$,we prove when $n\ge4 ,\dfrac{1}{\phi^n-\phi^{-n}} <q^n \iff q^n(\phi^n-\phi^{-n})>1 $

$f(x)=q^x(\phi^x-\phi^{-x}),f'(x)=\phi^xq^x \ln{(q\phi)}+\phi^{-x}q^x \ln{\dfrac{\phi }{q}} ,q\phi=1.009>1\implies f'>0,f(4)=1.017>1$

$\sum_{n=1}^{\infty}nq^n=\dfrac{q}{(1-q)^2}=4.413762 ,\sum_{n=4}^{\infty}nq^n=4.413762-(q+2q^2+3q^3)=2.282099$

$\dfrac{1}{F_{1}}+\dfrac{2}{F_{2}}+\dfrac{3}{F_{3}}+\sum_{k=4}^{n}\dfrac{k}{F_k}<1+2+1.5+\sqrt{5}*2.282099=9.602<10$

Answer 5

Clearly: $F_n > F_{n-1}$, for $n \geq 3$

Thus, $F_n = F_{n-1} + F_{n-2} > 2*F_{n-2} > 2^2*F_{n-4}>...>2^{(n-3)/2}*F_3 = 2^{(n-1)/2}$

Now, your inequality can be written as: $\sum\limits_{i=3}^n \frac{i}{F_i} < 10$

The $LHS < \sum\limits_{i=3}^n \frac{i}{2^{(i-1)/2}} = 2^{1/2}*\sum\limits_{i=3}^n \frac{i}{2^{i/2}} < 2^{1/2}*\sum\limits_{i=3}^\infty \frac{i}{2^{i/2}} = 2^{1/2}*\sum\limits_{i=3}^\infty f(i)$

It suffices to prove that $\sum\limits_{i=3}^\infty f(i) < 5*2^{1/2}$

It's easy to verify that $f(i)$ is non-negative, monotone decreasing on $[3;\infty)$, thus integral test is applicable and we have: $\sum\limits_{i=3}^\infty f(i) \leq f(3)+ \int_{3}^{\infty} f(x)dx = \frac{3}{2^{3/2}}+ \frac{1+3*\ln a}{(\ln a)^2}*a^{-3} = 7.06457 < 7.0710 = 5*2^{1/2}$, where $a=2^{1/2}$.

This upper approximation is far worse than that of Simon Rose.

Answer 6

This is only a partial answer, an effort to find an upper bound in terms of closed expressions.

Let $\alpha=\frac{1+\sqrt 5}{2},\ \beta=\frac{1-\sqrt 5}{2},\ \gamma=\frac{\beta }{\alpha} $. Note that $$\frac{k}{F_k}=\frac{k(\alpha-\beta)}{\alpha^k-\beta^k}=\frac{k/\alpha^{k-1}(1-\gamma)}{1-\gamma^{k}}=k(1-\gamma)\sum_{l\ge 0}\frac{\gamma^{kl}}{\alpha^{k-1}}\\\implies \sum_{k=1}^n \frac{k}{F_k}<\sum_{k=1}^\infty \frac{k}{F_k}=(1-\gamma)\sum_{k=1}^\infty\sum_{l=0}^{\infty}\frac{k\gamma^{kl}}{\alpha^{k-1}}\\ =(1-\gamma)\sum_{l=0}^{\infty}\gamma^l\sum_{k=0}^\infty \frac{(k+1)\gamma^{kl}}{\alpha^k} $$ Now, $$\sum_{k=0}^\infty(k+1) \frac{\gamma^{kl}}{\alpha^k}=\frac{1}{\left(1-\frac{\gamma^l}{\alpha}\right)^2}$$ Hence $$\sum_{k=1}^n \frac{k}{F_k}<(1-\gamma)\sum_{l\ge 0}\frac{\gamma^l}{\left(1-\frac{\gamma^l}{\alpha}\right)^2}$$ It remains to find an upper bound of the expression $S=\displaystyle \sum_{l\ge 0}\frac{\gamma^l}{\left(1-\frac{\gamma^l}{\alpha}\right)^2}$. Note that the series converges absolutely by Cauchy's root test.

Edit: We can find an upper bound of $S$ as below: Since $\gamma<0$, let $\gamma=-\delta$ where $\delta>0$. Then, $$S=\sum_{l\ge 0}\frac{\gamma^{2l}}{\left(1-\frac{\gamma^{2l}}{\alpha}\right)^2}-\sum_{l\ge 0}\frac{\delta^{2l+1}}{\left(1+\frac{\delta^{2l+1}}{\alpha}\right)^2}=A-B$$ Since $|\gamma|<1$, we have $\gamma^{2l}<1\ \forall l\ge 0\implies$ $$A<\frac{\sum_{l\ge 0}\gamma^{2l}}{\left(1-\frac{1}{\alpha}\right)^2}=\frac{\alpha^2}{(1-\gamma^2)(\alpha-1)^2}$$ Also, $|\delta|<1\implies$ $$-B<-\frac{\sum_{l\ge 0}\delta^{2l+1}}{\left(1+\frac{1}{\alpha}\right)^2}=\frac{\gamma\alpha^2}{(1-\gamma^2)(1+\alpha)^2}$$ Hence, $$\sum_{k=1}^n \frac{k}{F_k}<(1-\gamma)S<(1-\gamma)\alpha^2\frac{((1+\alpha)^2+\gamma(1-\alpha)^2)}{(1-\gamma^2)(\alpha^2-1)^2}\\=\frac{\alpha^2(1-2\alpha+5\alpha^2)}{(\alpha^2-1)^2}=\frac{15+3\sqrt{5}}{2}\approx 10.854$$