4
$\begingroup$

One of the interesting limits that I came up with is:

$$\lim_{n\to\infty} \frac{F_{n}}{B_{n}}\;\;\;\;\;\;\;\;\;\; \left( n \in \mathbb N^+\right)$$

Where $F_n$ is the nth Fibonacci number and $B_n$ is the nth Bell number.


If $n$ is a natural odd number then it can be written as $n=2k-1$ , where $k\in \mathbb N^+$, Using Stirling's approximation for the double factorial denoted $n!!=\left(2k-1\right)!!$ and the relation $B_{n}\ge n!!$ we have: $$0<\frac{F_{n}}{B_{n}} <\frac{F_{n}}{n!!}\sim \frac{\left(\frac{1+\sqrt{5}}{2}\right)^{2k-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{2k-1}}{\sqrt{5}}\cdot\frac{2^{k}\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}}{\sqrt{4\pi k}\left(\frac{2k}{e}\right)^{2k}}<\frac{2\cdot2^{k}}{k^{k}}$$

Taking the limit as $k \to \infty$ and using squeeze theorem follows: $$\lim_{n\to\infty} \frac{F_{n}}{B_{n}}=0$$

Which means as $n$ gets larger,the fraction with the numerator counting the number of ways to tile a board of size $1×n$ with squares and dominoes of size $1×1$ and $1×2$ respectively and the dinominator counting all possible partitions of a set with cardinality $n+1$ gets smaller.

The same can be done for $n$ even. For more information refer to this link.


Note: I've already proved that for all $k \in \mathbb N$ the relation $B_k\ge F_k$ holds, using this we conclude that:$$0<\frac{F_{n}}{B_{n}}\le1$$


The question is that: does there exist a more elegant way to prove this convergence?

$\endgroup$
5
  • $\begingroup$ $(3/2)^n < F_n \sim \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^n < 2^n$ but I think you're already using something like that. $\endgroup$ Mar 19 '20 at 16:47
  • 1
    $\begingroup$ Since both $F_n$ and $B_n$ are always positive, you don't need to give that lower bound for $F_n/B_n.$ $\endgroup$
    – Kenta S
    Mar 19 '20 at 17:05
  • $\begingroup$ @ kenta,then how should I use squeeze theorem? $\endgroup$
    – user715522
    Mar 19 '20 at 17:11
  • $\begingroup$ You already know $F_n/B_n>0$ $\endgroup$
    – Kenta S
    Mar 19 '20 at 17:25
  • $\begingroup$ @ Kenta S , you are totally right, I will edit that, thanks. $\endgroup$
    – user715522
    Mar 19 '20 at 17:26
4
$\begingroup$

Sicne $F_n\le 2^n$ and $B_n\ge n!!,$ we can say that $F_n/B_n\le 2^n/n!!.$ Since it is easily proven inductively that for large enough $n$ ($n\ge 21$), $n!!\ge 3^n,$ we have that, for large enough $n,$ $0<F_n/B_n\le 2^n/n!!\le 2^n/3^n=(2/3)^n.$ Now use Squeeze Theorem.

$\endgroup$
3
  • $\begingroup$ Can you please prove the inequality? $\endgroup$
    – user715522
    Mar 19 '20 at 17:45
  • $\begingroup$ I will prove the inequality when $n$ is even, as the odd case is exactly the same. First of all, $20!!\ge 3^20,$ as can be checked by a calculator. Now let $n>20$ be an even number, and assume the inequality for $n-2.$ We have that $n!!=n\cdot (n-2)!\ge n\cdot 3^{n-2}\ge 9\cdot 3^{n-2}=3^n.$ By induction, the inequality is proven for all even $n.$ $\endgroup$
    – Kenta S
    Mar 19 '20 at 17:49
  • $\begingroup$ Thanks, I just think it should be $n!!=n\cdot\left(n-2\right)!!$ instead of $n!!=n\cdot\left(n-2\right)!$ $\endgroup$
    – user715522
    Mar 19 '20 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy