How to prove $\lim_{n\to\infty}\frac{\log_{2}{(f_{n})}}{(\log_{2}{n})^2}=\frac{1}{2}$?

Question

For any $n\in N$, such $f_{1}=1$, and such

$$f_{2n+1}=f_{2n}=f_{2n-1}+f_{n},$$

prove that $$\lim_{n\to\infty}\dfrac{\log_{2}{(f_{n})}}{(\log_{2}{n})^2}=\dfrac{1}{2}.$$

Answer 1

Define $\left(~\mbox{with}\quad z \in {\mathbb C} \quad\mbox{and}\quad \left\vert z \right\vert < 1~\right)$ $$ \Psi\left(z\right) \equiv \sum_{n = 0}^{\infty}z^{n}\,{\rm f}_{n + 1} = \sum_{\sigma = \mp}\Psi_{\pm}\left(z\right) \quad\mbox{where}\quad\left\vert% \begin{array}{rcl} \Psi_{-}\left(z\right) & \equiv & \sum_{n = 0}^{\infty}z^{2n + 1}\,{\rm f}_{2n + 2} \\ \Psi_{+}\left(z\right) & \equiv & \sum_{n = 0}^{\infty}z^{2n}\,{\rm f}_{2n + 1} \\ {\rm f}_{n} & = & \left. {1 \over \left(n - 1\right)!}\, {{\rm d}^{n - 1}\,\Psi\left(z\right) \over {\rm d}z^{n - 1}} \right\vert_{z\ =\ 0}\,, \quad n > 1 \end{array}\right. $$

\begin{eqnarray} &&\\[5mm] \Psi_{-}\left(z\right) & = & \sum_{n = 0}^{\infty}z^{2n + 1}\,{\rm f}_{2n + 2} = \sum_{n = 0}^{\infty}z^{2n + 1}\left\lbrack{\rm f}_{2n + 1} + {\rm f}_{n + 1}\right\rbrack = z\left\lbrack\Psi_{+}\left(z\right) + \Psi\left(z^{2}\right)\right\rbrack \\ \Psi_{+}\left(z\right) & = & {\rm f}_{1} + \sum_{n = 0}^{\infty}z^{2n + 2}\,{\rm f}_{2n + 3} = 1 + \sum_{n = 0}^{\infty}z^{2n + 2}\,{\rm f}_{2n + 2} = 1 + z\,\Psi_{-}\left(z\right) \end{eqnarray}

$$ \Psi\left(z\right) = z\,\Psi\left(z\right) + 1 + z\,\Psi\left(z^{2}\right) \quad\Longrightarrow\quad \left(1 - z\right)\,\Psi\left(z\right) = 1 + z\,\Psi\left(z^{2}\right) $$

$$ \Psi^{\left(n\right)}\left(0\right) = n\,\Psi^{\left(n - 1\right)}\left(0\right) + \left.n\,\Psi^{\left(n - 1\right)}\left(z^{2}\right)\right\vert_{z\ =\ 0}\,, \qquad n \geq 1 $$

$$ \begin{array}{rclrcl} \Psi\left(z^{2}\right) & = & \sum_{n = 0}^{\infty}z^{2n}\,{\rm f}_{n + 1} ,\quad& \Psi\left(0\right) & = & {\rm f}_{1} \\ \Psi''\left(z^{2}\right) & = & 2\sum_{n = 1}^{\infty}n\left(2n - 1\right)z^{2n - 2}\,{\rm f}_{n + 1} ,\quad& \Psi\left(0\right) & = & 2{\rm f}_{2} \\ \Psi^{\left(\tt IV\right)}\left(z^{2}\right) & = & 2\sum_{n = 2}^{\infty}n\left(2n - 1\right)\left(2n - 2\right)\left(2n - 3\right)z^{2n - 4}\, {\rm f}_{n + 1} ,\quad& \Psi\left(0\right) & = & 16{\rm f}_{3} \\ &\vdots& & \vdots& \end{array} $$

$$ \left.\Psi^{\left(2n\right)}\left(z^{2}\right)\right\vert_{z = 0} = {\rm f}_{n + 1} $$

Answer 2

\documentclass[winfonts,hyperref,a4paper]{ctexart} \usepackage{mathrsfs} \usepackage{amscd} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsthm} \usepackage{graphicx} \usepackage[left=2.54cm,right=2.54cm,top=3.17cm,bottom=3.17cm]{geometry} \theoremstyle{plain} \newtheorem{pro}{Proposition} \linespread{1.39} \author{} \date{} \begin{document} \zihao{5} \pagestyle{empty} \thispagestyle{empty}

\begin{pro} Let$g(x)$be an strictly increasing continuous function in the interval$[0,+\infty)$ and $g(0)=0$,$g(x)0$.If an integer-valued finite terms sequence $P_{n}$satisfies the conditions below (1) if $P_{i}=x$,then $P_{i+1}\le g^{-1}(x)$;(2)the last term $P_{n}=n$.then the numbers of the sequence $P_{n}$ is$a_n=1+\sum_{i=1}^{[g(n)]} a_i$.

\end{pro} \begin{proof} If $P_{n}$has only one term,then $a_{n}\equiv 1$\

If$P_{n}$has at least two terms, then the second to last may be any one of$[g(n)],[g(n)]-1,\cdots,1$. \ Thus $a_n=1+\sum_{i=1}^{[g(n)]} a_i$.

\end{proof}

\begin{pro} $n\in N$,$f_{1}=1$,$f_{2n+1}=f_{2n}=f_{2n-1}+f_{n}$.

then

(0)$f_n$ is an integer-valued finite terms sequence and the last term is $n$.Moreover ,$\forall n\le 1,f_(n+1)\le f_n$.

(1)$f_{n}=1+\sum_{i=1}^{[\frac{n}{2}]}f_i$.

(2)If $f(x)=1+f_1x+f_2x^2+\cdots$ is the generating function of $f_n$,then $f(x)$ is an unique solution to functional equation of$f(x^2)=(1-x)f(x)$

(3)$f(x)=\Pi_{k=0}^{+\infty} \frac{1}{1-y^{2^k}}$.

(4)$f_n$ is numbers of nonnegative integer solutions to $n=j_1+2j_2+4j_3+8j_4+16j_5+\cdots$.

(5)$\lim_{n\to\infty}\dfrac{\log_{2}{(f_{n})}}{(\log_{2}{n})^2}=\dfrac{1}{2}$ \end{pro}

\begin{proof}(0)Proposition 1 implies it.

(1)Notice\begin{align*} f_{2n+1}=f_{2n}&=f_{2n-1}+f_{n}=f_{2n-2}+f_{n} \\&=f_{2n-3}+f_{n-1}+f_n \\&=f_{2n-5}+f_{n-2}+f_{n-1}+f_n \\&=\cdots \\&=f_1+f_1+f_2+\cdots+f_{n-1}+f_n \\&=1+\sum_{k=1}^nf_k \end{align*}

(2)Direct check.

\begin{align*} (1+f_1x+f_2x^2+\cdots)(1+x+x^2+\cdots)&=1+(1+f_1)x+(1+f_1+f_2)x^2+\cdots \\&=1+f_2x^2+f_4x^2+\cdots=1+\sum_{n=1}^{+\infty}f_{2n}x^n \\&=1+f_3x^2+f_4x^2+\cdots=1+\sum_{n=1}^{+\infty}f_{2n+1}x^n \end{align*} $$f(\sqrt{x})=1+f_1\sqrt{x}+f_2(\sqrt{x})^2+\cdots$$ $$f(-\sqrt{x})=1-f_1\sqrt{x}+f_2(\sqrt{x})^2+\cdots$$ then$$\frac{f(x)}{1-x}=\frac{f(\sqrt{x})+f(-\sqrt{x})}{2}=\frac{f(\sqrt{x})-f(-\sqrt{x})}{2\sqrt{x}}$$

set $x=y^2$,then $$\frac{f(y^2)}{1-y^2}=\frac{f(y)+f(-y)}{2}=\frac{f(y)-f(-y)}{2y}$$ Thus$f(-y)=\frac{1-y}{1+y}f(y)$,which implies $f$ satisfies $f(y^2)=(1-y)f(y)$.

(3):By(2)\begin{align*} f(y)&=\frac{f(y^{2^n})}{(1-y)(1-y^2)(1-y^4)\cdots(1-y^{2^{n-1}})} \\&=\lim_{n\to+\infty} \frac{f(y^{2^n})}{\Pi_{i=0}^{n-1}(1-y^{2^i})}=\Pi_{k=0}^{+\infty} \frac{1}{1-y^{2^k}} \end{align*}

(4)Because \begin{align*} f(y)= \Pi_{k=0}^{+\infty}\sum_{j=0}^{+\infty} y^{2^kj}=\sum_{n=0}^{+\infty}\sum_{\sum_{i=0}^{+\infty}2^{i-1}j_i=n}y^n \end{align*} Thus $f_n$ is numbers of nonnegative integer solutions to $n=j_1+2j_2+4j_3+8j_4+16j_5+\cdots$. Obviously $f_n$ is increasing.

(5)Consider $n=2^k$,we try to give out an estimation of numbers of nonnegative integer solutions to $2^k=j_1+2j_2+4j_3+8j_4+\cdots+2^kj_{k+1}$.

Note $j_1$has at most$2^{k+1}$ choices ,$j_2$has at most$2^{k}$choices,……,$j_{k+1}$has at most$2$choices.Then numbers of nonnegative integer solutions have at most$2^{k+1}\cdot 2^k\cdot \cdots\cdot 2=2^{\frac{(k+2)(k+1)}{2}}$choices.

Thus $f_{2^k}\leq 2^{\frac{(k+2)(k+1)}{2}}$,or $\log_2 f_{2^k}\leq\frac{(k+2)(k+1)}{2}$,or $\overline{\lim}_{k\to+\infty}\frac{\log_2 f_{2^k}}{k^2}\leq \frac{1}{2}$.

Similarly $\underline{\lim}_{k\to+\infty}\frac{\log_2 f_{2^k}}{k^2}\geq \frac{1}{2} $.

Thus $\lim_{k\to+\infty}\frac{\log_2 f_{2^k}}{k^2}= \frac{1}{2}$.

If $2^k\leq n< 2^{k+1}$,$f_{2^k}\leq f_n\leq f_{2^{k+1}}$,then $$\frac{\log_2 f_{2^k}}{k^2}\frac{k^2}{(\log_2 n)^2}\leq\frac{\log_2 f_n}{(\log_2 n)^2}\leq \frac{\log_2 f_{2^{k+1}}}{(k+1)^2}\frac{k^2}{(\log_2 n)^2}$$ let $n\to+\infty$,$k\to \infty$,thus$$\lim_{n\to\infty}\frac{\log_{2}{(f_{n})}}{(\log_{2}{n})^2}=\frac{1}{2}$$ \end{proof} By the way ,the problem has close connection with analytical number theory(it can be proved in analytical number theory way which is quite concise.)Of course my friend tell me about the analytical number theory approach.Could you tell me the original source or links to the problem?I'm interested in it.Thanks for your problem. \end{document}