g(n)表示n的最大奇因数,如g(9)=9,g(10)=5.那么g(1)+g(2)+g(3)+⋯+g(22015−1)=_____.
解 根据g(n)的定义有g(n)={n,n为奇数,g(n2),n为偶数.
递归是解决数列问题的一个常见思路,其中有递归结构的一个著名的问题是汉诺塔问题,这个问题是这样的:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针.印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔.不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面.僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽. 假设每秒钟可以移动一个金片,那么预言中的世界末日何时到来呢? 假设金片数量为n时,把一根针上的金片移动到另外一根针上需要an秒,则an就满足递推关系an=2an−1+1,n⩾2
注 汉诺塔问题参考百度百科.
最后给出一道练习:
数列{2n−1}的前n项1,3,7,⋯,2n−1组成集合An={1,3,7,⋯,2n−1}(n∈N∗),从集合An中任取k(k=1,2,⋯,n)个数,其所有可能的k个数的乘积的和为Tk(若只取一个数,规定乘积为此数本身),记Sn=T1+T2+⋯+Tn.例如当n=1时,A1={1},T1=1,S1=1;当n=2时,A2={1,3},T1=1+3,T2=1×3,S2=1+3+1×3=7.则Sn=_______.
答案 2n(n+1)2−1.
提示 可以得到Sn满足的递推关系Sn=Sn−1+(2n−1)+(2n−1)⋅Sn−1,n⩾2
注 练习题另外一种解法见每日一题[308] 山重水复疑无路,似曾相识燕归来.递归结构的另外一个著名的例子是卡特兰数.