数列 $\{a_n \}$ 满足 $a_1 =1$，且 $a_{2k}=a_{2k-1} + a_k$，$a_{2k+1}=a_{2k}$，（$k=1,2,\ldots $）．
证明：对任意整数 $n$，有 $a_{2^n}<2^{\frac{n^2}{2}}$．
证明：对任意整数 $n$，有 $a_{2^n}<2^{\frac{n^2}{2}}$．
【难度】
【出处】
2015中国东南数学奥林匹克试题(高二)
【标注】
【答案】
略
【解析】
由条件知，数列 $\{a_n \}$ 单调不减．
进一步可知，对任意整数 $s,t(0\leqslant t< s)$，有
$a_{s+t+1}-a_{s-t}\geqslant a_{s+t}+a_{s+1-t}$ ①
事实上，若 $s,t$ 奇偶性相同，则 $s\pm t$ 为偶数，故
$a_{s+t+1}=a_{s+t},a_{s-t}=a_{s+1-t}$
因此 ① 成立（这时 ① 的两边相等）；
若 $s,t$ 奇偶性不同，则 $s+1\pm t$ 为偶数，故
$\left(a_{s+t+1}+a_{s-t}\right)-\left(a_{s+t}+a_{s+1-t}\right)=\left(a_{s+t+1}+a_{s+t}\right)-\left(a_{s+1+t}+a_{s-t}\right)=a_{\tfrac{s+t+1}{2}}-a_{\tfrac{s+1+t}{2}}\geqslant 0$
这时 ① 也成立．
利用 ① 得，$a_{2 s}+a_{1} \geqslant a_{2 s-1}+a_{2} \geqslant \cdots \geqslant a_{s+1}+a_{s}$，故有
$a_{1}+a_{2}+\cdots+a_{2 s} \geqslant s\left(a_{s+1}+a_{s}\right) \geqslant 2 s a_s$
另一方面，根据条件知
$\begin{aligned} & a_{1}+a_{2}+\cdots+a_{2 s} \\=& \sum_{i=1}^{2 s}\left(a_{2 i}-a_{2 i-1}\right) \\=& a_{4 s}-\left(\sum_{i=1}^{2s-1}\left(a_{2 i+1}-a_{2 i}\right)\right)-a_{1}<a_{4 s} \end{aligned}$
比较上述两式知，$a_{4s}>2sa_s$，特别地，当 $s=2^{m-2}(m \geqslant 2)$ 时，有 $a_{2^{m}}>2^{m-1} a_{2^{m-2}}$ ②
下面用数学归纳法证明 $a_{2^m}>2^{\tfrac{n^2}{4}}(n\in N^{\ast})$
当 $n=1,2$ 时，有 $a_{2}=2>2^{\tfrac{1^2}{4}}, a_{4}=4>2^{\tfrac{2^2}{4}}$ 成立．
若当 $n=m-2$ 时结论成立，则由 ② 即归纳假设知
$a_{2}>2^{m-1} a_{2^{m-2}}>2^{m-1+\frac{(m-2)^{2}}{4}}=2^{\frac{m^2}{4}}$
故结论对 $n=m$ 亦成立．从而对一切正整数 $n$，均有 $a_{2^n}>2^{\frac{n^2}{4}}$．
进一步可知，对任意整数 $s,t(0\leqslant t< s)$，有
$a_{s+t+1}-a_{s-t}\geqslant a_{s+t}+a_{s+1-t}$ ①
事实上，若 $s,t$ 奇偶性相同，则 $s\pm t$ 为偶数，故
$a_{s+t+1}=a_{s+t},a_{s-t}=a_{s+1-t}$
因此 ① 成立（这时 ① 的两边相等）；
若 $s,t$ 奇偶性不同，则 $s+1\pm t$ 为偶数，故
$\left(a_{s+t+1}+a_{s-t}\right)-\left(a_{s+t}+a_{s+1-t}\right)=\left(a_{s+t+1}+a_{s+t}\right)-\left(a_{s+1+t}+a_{s-t}\right)=a_{\tfrac{s+t+1}{2}}-a_{\tfrac{s+1+t}{2}}\geqslant 0$
这时 ① 也成立．
利用 ① 得，$a_{2 s}+a_{1} \geqslant a_{2 s-1}+a_{2} \geqslant \cdots \geqslant a_{s+1}+a_{s}$，故有
$a_{1}+a_{2}+\cdots+a_{2 s} \geqslant s\left(a_{s+1}+a_{s}\right) \geqslant 2 s a_s$
另一方面，根据条件知
$\begin{aligned} & a_{1}+a_{2}+\cdots+a_{2 s} \\=& \sum_{i=1}^{2 s}\left(a_{2 i}-a_{2 i-1}\right) \\=& a_{4 s}-\left(\sum_{i=1}^{2s-1}\left(a_{2 i+1}-a_{2 i}\right)\right)-a_{1}<a_{4 s} \end{aligned}$
比较上述两式知，$a_{4s}>2sa_s$，特别地，当 $s=2^{m-2}(m \geqslant 2)$ 时，有 $a_{2^{m}}>2^{m-1} a_{2^{m-2}}$ ②
下面用数学归纳法证明 $a_{2^m}>2^{\tfrac{n^2}{4}}(n\in N^{\ast})$
当 $n=1,2$ 时，有 $a_{2}=2>2^{\tfrac{1^2}{4}}, a_{4}=4>2^{\tfrac{2^2}{4}}$ 成立．
若当 $n=m-2$ 时结论成立，则由 ② 即归纳假设知
$a_{2}>2^{m-1} a_{2^{m-2}}>2^{m-1+\frac{(m-2)^{2}}{4}}=2^{\frac{m^2}{4}}$
故结论对 $n=m$ 亦成立．从而对一切正整数 $n$，均有 $a_{2^n}>2^{\frac{n^2}{4}}$．
答案
解析
备注
