【正确答案】先对固定的非负整数b,用归纳法证明等式
fa+b=fa-1fb+fafb+1
事实上,对a=1,等式右端=fafb+f1fb+1=fb+1=等式左端。假设a≤k时等式成立,则当a=k+1时
fk+1+b=fk+b+fk+b-1=(fk-1fb+fkfb+1)+(fk-2fb+fk-1fb+1)=
(fk-1+fk-2)fb+(fk+fk-1)fb+1=fkfb+fk+1fb+1
等式成立。
设m=nk,对k应用归纳法证明。当k=1时,fm=fn,即fm可被fn整除。假设k=K时结论成立,则当k=K+1时,根据上面已证明的等式,fn(K+1)=fn+nK=fn-1fnK+fnfnK+1,即fn(K+1)可被fn整除。
【答案解析】