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

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

Solution 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.)

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

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