高中数学竞赛题——数列a0=0 a1=1 an=2a(n-1)+a(n-2)证明 若2^k整除an,则2^k整除n必须要这么硬算吗？

高中数学竞赛题——数列a0=0 a1=1 an=2a(n-1)+a(n-2)证明 若2^k整除an,则2^k整除n必须要这么硬算吗？
高中数学竞赛题——数列
a0=0 a1=1 an=2a(n-1)+a(n-2)
证明 若2^k整除an,则2^k整除n
必须要这么硬算吗？

高中数学竞赛题——数列a0=0 a1=1 an=2a(n-1)+a(n-2)证明 若2^k整除an,则2^k整除n必须要这么硬算吗？
首先注意到,由所给递推关系,
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]
对任意0a[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 2^k|n；否则从上述推理可得2^(k-a)|a[m].但是由最初的论断,a[m]是奇数,于是k=a,进而2^k|n.

先用特征方程求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的通项
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

收起