F(n) = F(n-1) - F(n-2)

Question

我在一次编程竞赛中遇到了这个序列F(n)= F(n-1)-F(n-2)；给定F0和F1找到第n项

(http://codeforces.com/contest/450/problem/B) (比赛结束)

现在这个问题的解决方案是这样的，序列取值f0，f1，f1- f0，-f0，-f1，f0 - f1，然后再次f0，整个序列重复。

我得到了这个值正在重复，但找不到这个循环顺序的原因。我搜索了循环顺序和序列，但由于循环的原因，我找不到足够的材料来给人真实的感觉。

Answer 1

解决这个问题的另一种方法。请注意，F(n) = F(n - 1) - F(n - 2)与F(n) - F(n - 1) + F(n - 2) =0相同，这使得它是一个线性差分方程。这类方程有基本解a^n，其中a是多项式的根:设F(n) = a^n，则a^n - a^(n - 1) + a^(n - 2) = (a^2 -a+ 1)*a^(n - 2) = 0，因此a^2 -a+1=0有两个复根(你可以找到它们)，它们的幂为1，a，a^2，a^3，……绕单位圆移动，在2pi/(pi/3)=6步后返回到1。

这种分析与微分方程的相应分析具有相同的缺陷--您如何知道如何寻找某种类型的解？我不知道这个问题的答案，也许别人有。同时，当你看到一个线性差分方程时，想想a^n形式的解。

Answer 2

如果将原始公式应用于n-1

F(n -1) = F(n-2) - F(n -3) 

然后，如果我替换原始F(n)表达式中的F(n-1

F(n) = F(n-2) - F(n -3) - F(n-2) = -F(n - 3)
F(n) = - F(n-3)

因为如果我将n替换为n-3，后者也是有效的

F(n - 3) = - F(n -6)

将后两者结合起来

F(n) = -(-F(n-6)) = F(n-6)

因此，序列是周期为6的周期性序列