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

如果将原始配方用于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-3替换n,后者也是有效的

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

结合最后两个

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

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

Answer 2

解决此问题的另一种方法。请注意，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，自变量pi / 3。因此，它们的幂1，a，a ^ 2，a ^ 3，...围绕单位圆传播，并在2 pi /（pi / 3）= 6步之后返回1。

此分析与微分方程式的分析存在相同的缺陷-您如何知道寻找某种解？我没有答案，也许有人回答。同时，每当您看到线性差分方程时，请考虑a ^ n形式的解。