2

I came across this sequence in a programming contest F(n)= F(n-1)-F(n-2); Given F0 and F1 find nth term

(http://codeforces.com/contest/450/problem/B) (the contest is over)

Now the solution of this problem is like this The sequence take value f0, f1, f1-f0, -f0, -f1, f0 - f1 then again f0 and the whole sequence is repeated.

I get that this value is being repeated but could not found the reason for this cyclic order. I searched for cyclic order and sequences but could not find sufficient material that could give the actual feel for the reason of the cycle.

4

2 回答 2

7

如果将原始公式应用于 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)

因此序列是循环的,周期为六

于 2015-05-30T17:32:02.867 回答
5

解决这个问题的另一种方法。请注意,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 形式的解。

于 2015-05-30T18:57:34.680 回答