一个单调不减的数列

hbghlyj

数列{$a_n$}满足$a_1=1,a_{2k}=a_{2k-1}+a_{k},a_{2k+1}=a_{2k}$,证明：对于正整数$n\geq3$,均有$a_{2^n}\lt2^{\frac{n^2}{2}}$

realnumber

数学归纳法可以写的
$a_8=a_9=10<16<2^{n^2/2}$,记$t=2^{n-1}$
\[a_{2^n}=a_{2^n-1}+a_t=a_{2^n-2}+a_t=a_{2^n-4}+(a_{t-1}+a_t)=a_{2^n-6}+(a_{t-2}+a_{t-1}+a_t)\]
\[......\]
\[a_{2^n}=a_{2^n-t}+(a_{t-2^{n-2}+1}+...+a_{t-2}+a_{t-1}+a_t)<2^{\frac{(n-1)^2}{2}}(2^{n-2}+1)\]
只要证明$2^{\frac{(n-1)^2}{2}}(2^{n-2}+1)<2^{\frac{n^2}{2}}$
即要证明$2^{n-2}+1<2^{n-1}<2^{n-0.5}$,完

hbghlyj

回复 2# realnumber 易知{$a_n$}是一个单调不减的数列，对于$i \geq 2, a_{2i}-a_{2i-2}=\left(a_{2i-1}+a_{i}\right)-a_{2i-1}=a_{i}$
$a_{2^{m+1}}-a_{2^m}=\sum_{i=2^{m-1}+1}^{2^{m}}\left(a_{2 i}-a_{2i-2}\right)=\sum^{2^m}_{i=2^{m-1}+1}a_i \leq 2^{m-1}a_{2^m}$
从而$\frac{a_{2^{m+1}}}{a_{2^m}}\leq2^{m-1}+1\lt2^m$
对于任意正整数$n \geq3$,都有$a_{2^n}=a_4 \prod^{n-1}_{m=2}\frac{a_{2^{m+1}}}{a_{2^m}}\lt4\prod^{n-1}_{m=2}2^m\lt2^{\frac{n^2}2}$