Fibonacci数列 存在$n∣F_{F_n}$但$n\nmid F_n$.

hbghlyj

(a)$\log_{F_{n-1}}{F_n}<\frac{n-1}n<\log_{F_n}{F_{n+1}}$
artofproblemsolving.com/community/c6h2562573p21963641
math.stackexchange.com/questions/4139629/
math.stackexchange.com/questions/4140618/

(b)存在无穷多个正整数n,使得$n∣F_{F_n}$但$n\nmid F_n$.
komal Problem A. 730. (September 2018)
证明:我们证明$n=4\cdot3^k\cdot23$(k≥1)满足要求.
引理1.若$3\big|F_n$,则$ v_3(F_{3n})=v_3(F_n)+1$
证明:记$\varphi=\frac{1+\sqrt5}2,\psi=\frac{1-\sqrt5}2,$则
$F_{3n} = \frac{\varphi^{3n}-\psi^{3n}}{\sqrt5}
= \frac{(\varphi^n-\psi^n)^3+3\varphi^n\psi^n(\varphi^n-\psi^n)}{\sqrt5}
= 5\bigg(\frac{\varphi^n-\psi^n}{\sqrt5}\bigg)^3+3(\varphi\psi)^n\frac{\varphi^n-\psi^n}{\sqrt5}
= 5F_n^3+3(-1)^nF_n.$
$v_3(5F_n^3)=3v_3(F_n)>v_3(F_n)+1=v_3(3(-1)^nF_n)$.引理1得证.
引理2.对任意$n\in\mathbb N$有$23\big|F_n \Leftrightarrow24\big|n$.
证明:$F_{24}=46368=2016\cdot 23$是Fibonacci数列中最小的23的倍数.若$24\big|n$,则$23\big|F_{24}\big|F_n$;
若$24\nmid n$,假设$23\big|F_n$,则$d=\operatorname{gcd}(n,24)<24$,则$\operatorname{gcd}(F_n,23)\big|\operatorname{gcd}(F_n,F_{24})=F_d$.但$F_d<F_{24}$不可能是23的倍数.引理2得证.
回到原题,对于$n=4\cdot3^k\cdot23$(k≥1),由引理2,$\because24\not{\big|}n,\therefore 23\not{\big|}F_n,\therefore n\not{\big|}F_n$.
另一方面,由12|n得$24\mid 144=F_{12}\mid F_n$.
由$12\big|F_n$得$144=F_{12}\big|F_{F_n}$.
由$3=F_4$和引理1得$3^{k+1}\big|F_{F_n}$.
由$24\big|F_n$和引理2得$23\big|F_{F_n}$.
注:一般地,对于斐波那契数的迭代,设$F^k(n)=\underbrace{F(\ldots F}_k(n)\dots)$,我们证明,每个k≥2存在无穷多n使得$n\big|F^k(n)$,但n不整除$F(n),\ldots,F^{k-1}(n)$中的任何一个.设m使得$m\big|F_m$(例如$m=5^t$或$m=12\cdot 3^t$或$m=F^t(12)$等),设p是$F^k(m)$的本原素因子(当m足够大时有这样的素数,见Carmichael theorem),n=mp,则$m\big|F(m)\big|F^2(m)\big|\ldots\big|F^k(m)$,$p\big|F^k(m)$,所以$n\big|F^k(m)\big|F^k(n)$.
另一方面,对$1\le\ell<k$有$\gcd\big(F^\ell(n),n\big) \big| \gcd\big(F^\ell(n),F^k(n)\big) =
F^\ell\big(\gcd(F^{k-\ell}(n),n)\big),$这里$p\not\mid F^{k-\ell}(n)$,所以$\gcd\big(F^\ell(n),n\big) \Big| m,$所以$\gcd\big(F^\ell(n),n\big) \big| F^\ell\big(m)\big),$不是p的倍数.
Fibonacci数列的前300项的质因数分解

kuing

画图看了下似乎是
\[\log_{F_{n-1}}F_n>\frac{n-1}{n-2}>\log_{F_n}F_{n+1},\quad\forall n>3.\]
又或者写成
\[\frac{\ln F_n}{n-1}>\frac{\ln F_{n-1}}{n-2}\land\frac{\ln F_{n+1}}{n-1}<\frac{\ln F_n}{n-2},\]也就是说数列 `\bigl\{\frac{\ln F_n}{n-1}\bigr\}` 递增而 `\bigl\{\frac{\ln F_n}{n-2}\bigr\}` 递减。

但，怎么证哩？ωω

hbghlyj

(来自qianxiangzhen3)
记$\phi=\frac{1+\sqrt5}2$,不等式即$F_{n-1}^n<F_n^{n-1}$
$\Leftrightarrow \frac1{(\sqrt5)^n}\left[\phi^n-\left(-\frac1\phi\right)^n\right]^n<\frac1{(\sqrt5)^{n-1}}\left[\phi^{n+1}-\left(-\frac1\phi\right)^{n+1}\right]^{n-1}$
$\Leftrightarrow \left[1-\left(-\frac1{\phi^2}\right)^n\right]^n<\frac{\sqrt5}\phi\left[1-\left(-\frac1{\phi^2}\right)^{n+1}\right]^{n-1}$
n为偶数时,LHS$<1<\frac{\sqrt5}\phi<$RHS;n为奇数时,即
$\left(1+\frac1{\phi^{2n}}\right)^n<\frac{\sqrt5}\phi\left(1-\frac1{\phi^{2n+2}}\right)^{n-1}$
取对数,并由$\ln(1+x)<x,\ln(1-x)>-x-0.6x^2\quad\left(x\le\frac1{\phi^4}\right)$知只要证
$\frac1{\phi^{2n}}<\ln\frac{\sqrt5}\phi-(n-1)\cdot\frac1{\phi^{2n+2}}-0.6(n-1)\frac1{\phi^{4n+4}}$
正的项大于负的项的两倍,并且负的项的绝对值关于n递减,只要验证n=1.

色k

回复 3# hbghlyj

那 2# 的呢？

hbghlyj

色k 发表于 2021-2-27 05:45
回复 3# hbghlyj

那 2# 的呢？

math.stackexchange.com/questions/4140618
$F_n = \frac{1+\sqrt{5}}{2\sqrt{5}} \phi^n ( 1   + O(\eta^{n})) =: c \  \phi^n (1+O(\eta^n))$
$$ \frac{\log(F_n)}{\log(F_{n+1})} = \frac{n+ k +  O(\eta^n)}{n+1 +k+O(\eta^n)}  =: \frac{n+k_n}{1+n+k_n}$$
上述分析适用于任何序列 $x_n= c\ \phi^n(1+O(\eta^n)),\eta<1$，相应的 $k=\log(c)/\log(\phi)$.

hbghlyj

为什么$k_n -k =O(n \ \eta^n)$呀

hbghlyj

hbghlyj 发表于 2024-3-28 21:07
为什么$k_n -k =O(n \ \eta^n)$呀

由$k_n$的定义，
$$\frac{n+ k +  O(\eta^n)}{n+1 +k+O(\eta^n)}  = \frac{n+k_n}{1+n+k_n}$$
两边分母减去分子得，（注意$O(\eta^n)-O(\eta^n)=O(\eta^n)$，很容易搞錯成$=0$）
$$\frac{n+ k +  O(\eta^n)}{O(\eta^n)}  =\frac{n+k_n}{1}$$
就得到了原回答的$k_n -k =O(n \ \eta^n)$