Question

高中数学竞赛题——数列

a0=0 a1=1 an=2a(n-1)+a(n-2)
证明 若2^k整除an，则2^k整除n
必须要这么硬算吗？

Answer 1

首先注意到，由所给递推关系，
a[n]= 2a[n-1]+a[n-2]= a[n-2] (mod 2)
即a[n]与a[n-2]同奇偶。于是a[2n]是偶数，a[2n-1]是奇数。

下面证明，如果2^(k+1)|a[2n]，则2^k|a[n]。为此，注意到如下一系列转换关系：
a[n]
=2a[n-1]+a[n-2]
=a[2](2a[n-2]+a[n-3])+a[1]a[n-2]
=(2a[2]+a[1])a[n-2]+a[2]a[n-3]
=a[3]a[n-2]+a[2]a[n-3]
=...
=a[k]a[n-k+1]+a[k-1]a[n-k]
=a[k](2a[n-k]+a[n-k-1])+a[k-1]a[n-k]
=(2a[k]+a[k-1])a[n-k]+a[k]a[n-k-1]
=a[k+1]a[n-k]+a[k]a[n-k-1]
对任意0<k<n成立。特别地，
a[2n]
=a[n]a[n+1]+a[n-1]a[n]
=(a[n+1]+a[n-1])a[n]
=(2a[n]+a[n-1]+a[n-1])a[n]
=2(a[n]+a[n-1])a[n]
由此前所证，a[n]与a[n-1]必为一奇一偶，从而a[n]+a[n-1]是奇数。于是
2^(k+1)|2(a[n]+a[n-1])a[n] => 2^k|a[n]

现在，对任意的n，令n=(2^a)*m，其中a是非负整数，m是奇数。设2^k|a[n]，若k<a，则2^k|2^a => 2^k|n；否则从上述推理可得2^(k-a)|a[m]。但是由最初的论断，a[m]是奇数，于是k=a，进而2^k|n。

Answer 2

先用特征方程求an的通项
an=2a(n-1)+a(n-2)
对应的特征方程是 x^2=2x+1
解得 x=1+- √2
设 an=A(1+√2)^n+B(1-√2)^n
a0=0 a1=1代人得
A=√2/4 ,B=-√2/4
an=√2/4*[(1+√2)^n-(1-√2)^n]

（1+√2)^n，(1-√2)^n
用二项式定理展开得
an=√2/4*[(1+√2)^n-(1-√2)^n]
==√2/4{C(n,0)+C(n,1)*√2+.....C(n,n)(√2)^n-[C(n,0)-C(n,1)√2+......+C(n,n)(-√2)^n]}
=√2/4*{2C(n,1)*√2+2C(n,3)*(√2)^3+.....}
=√2/4*2√2[C(n,1)+C(n,3)*2+C(n,5)*2^2+.....]
=C(n,1)+C(n,3)*2+C(n,5)*2^2+....
显然，n为奇数时，an为奇数
2^k|an（k 不等于0） 则n比为偶数
an=n+n*2*1/3C(n-1,2)+n*2^2*1/5C(n-1,4)+.....n*2^(n/2)*1/(n-1)C(n-1,n-2)
= n*{1+2[1/3C(n-1,2)+1/5*2*C(n-1,4)+....2^(n/2-1)1/(n-1)C(n-1,n-2)}
显然1+2[1/3C(n-1,2)+1/5*2*C(n-1,4)+....2^(n/2-1)1/(n-1)C(n-1,n-2)}
不是2的整数倍
2^k不能整除1+2[1/3C(n-1,2)+1/5*2*C(n-1,4)+....2^(n/2-1)1/(n-1)C(n-1,n-2)}
故2^k|n