每日一题[328]世界末日

$g(n)$表示$n$的最大奇因数，如$g(9)=9$，$g(10)=5$．那么$g(1)+g(2)+g(3)+\cdots+g(2^{2015}-1)=$_____．

正确答案是$\dfrac {1}{4^{2015}-1}$．

解　根据$g(n)$的定义有 $$g(n)=\begin{cases} n,&n为奇数,\\g\left(\dfrac {n}{2}\right ),&n为偶数.\\\end{cases}$$ 记$S_n=g(1)+g(2)+g(3)+\cdots+g(2^n-1)$，则 $$\begin{split} S_n&=\left[g(1)+g(3)+\cdots+g(2^n-1)\right ]+\left[g(2)+g(4)+\cdots+g(2^{n}-2)\right ]\\&=\left[1+3+\cdots+(2^n-1)\right ]+\left[g(1)+g(2)+\cdots+g(2^{n-1}-1)\right ]\\&=4^{n-1}+S_{n-1}.\end{split}$$ 由累加法知 $$\begin{split} S_{2015}&=4^{2014}+4^{2013}+\cdots+4^1+1\\&=\dfrac 13\left(4^{2015}-1\right ).\end{split}$$ 本题很难直接找到$g(n)$的表达式，但从$g(n)$满足的递推关系入手就容易很多，因为$g(n)$具有很好的递归结构．

递归是解决数列问题的一个常见思路，其中有递归结构的一个著名的问题是汉诺塔问题，这个问题是这样的：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针．印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔．不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面．僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽． 假设每秒钟可以移动一个金片，那么预言中的世界末日何时到来呢？ 假设金片数量为$n$时，把一根针上的金片移动到另外一根针上需要$a_n$秒，则$a_n$就满足递推关系 $$a_{n}=2a_{n-1}+1,n\geqslant 2$$ 从而可以由不动点法求得数列$\{a_n\}$的通项公式为 $$a_n=2^n-1,$$ 所以 $$a_{64}=18446744073709551615$$ 秒，折成年约为$5845.54$亿年．

注　汉诺塔问题参考百度百科．

最后给出一道练习：

数列$\left \{2^n-1 \right \}$的前$n$项$1,3,7,\cdots,2^n-1$组成集合$A_n= \{1,3,7,\cdots,2^n-1 \}(n \in {\mathcal N^*})$，从集合$A_n$中任取$k$（$k=1,2, \cdots ,n$）个数，其所有可能的$k$个数的乘积的和为$T_k$（若只取一个数，规定乘积为此数本身），记$S_n=T_1+T_2+\cdots+T_n$．例如当$n=1$时，$A_1=\{1\}$，$T_1=1$，$S_1=1$；当$n=2$时，$A_2=\{1，3\}$，$T_1=1+3$，$T_2=1 \times 3$，$S_2=1+3+1 \times 3=7$．则$S_n=$_______．

答案　$2^{\frac{n(n+1)}{2}}-1$．

提示　可以得到$S_n$满足的递推关系 $$S_n=S_{n-1}+(2^n-1)+(2^n-1)\cdot S_{n-1},n\geqslant 2$$ 从而得到 $$\dfrac {S_n+1}{S_{n-1}+1}=2^n,$$ 由累乘法即可得到$S_n$的表达式．

注　练习题另外一种解法见每日一题[308] 山重水复疑无路，似曾相识燕归来．递归结构的另外一个著名的例子是卡特兰数．