设an(n是下脚标)为下述正整数N的个数：N的各位数字之和为n且每位数字都只能取134求证：对每个正整数n,a2n（2n是下脚标）都是完全平方数.[用最通俗的语言解释,不要复制粘贴,我就是书上的

Question

设an(n是下脚标)为下述正整数N的个数：
N的各位数字之和为n且每位数字都只能取1 3 4
求证：对每个正整数n,a2n（2n是下脚标）都是完全平方数.
[用最通俗的语言解释,不要复制粘贴,我就是书上的解释太抽象才问的]

Answer 1

首先,容易建立an的递推式:
an=a(n-1)+a(n-3)+a(n-4)
a1=1,a2=1,a3=2
把an前10项写出来:
a1=1
a2=1
a3=2
a4=4
a5=6
a6=9
a7=15
a8=25
a9=40
a10=64
我们惊异的发现
a2=1*1
a3=1*2
a4=2*2
a5=2*3
a6=3*3
a7=3*5
a8=5*5
a9=5*8
a10=8*8
联想斐波那契数列:
F1=1,F2=2,F3=3,F4=5,F5=8...F(n)=F(n-1)+F(n-2)
猜想:
a(2n-1)=F(n-1)*F(n)
a(2n)=F(n)*F(n)
数学归纳法证明:
1)n=2时显然成立
2)假设n≤k时命题成立
那么
a(2(n+1)-1)
=a(2n+1)=a(2n)+a(2n-2)+a(2n-3)
=F(n)*F(n)+F(n-1)*(F(n-1)+F(n-1)*F(n-2)
=F(n)*F(n)+F(n-1)*(F(n-1)+F(n-2))
=F(n)*F(n)+F(n-1)*F(n)
=F(n)*(F(n)+F(n-1))
=F(n)*F(n+1)
a(2(n+1))
=a(2n+1)+a(2n-1)+a(2n-2)
=F(n)*F(n+1)+F(n-1)*F(n)+F(n-1)*F(n-1)
=F(n)*F(n+1)+F(n-1)*(F(n)+F(n-1))
=F(n)*F(n+1)+F(n-1)*F(n+1)
=F(n+1)*(F(n)+F(n-1))
=F(n+1)*F(n+1)
n=k+1时也成立
总上所述命题成立,a2n=F(n)^2是完全平方数,得证