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

Question

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.

Solution 1

Another way to approach this problem. Note that F(n) = F(n - 1) - F(n - 2) is the same as F(n) - F(n - 1) + F(n - 2) = 0 which makes it a linear difference equation. Such equations have fundamental solutions a^n where a is a root of a polynomial: suppose F(n) = a^n, then a^n - a^(n - 1) + a^(n - 2) = (a^2 - a + 1)*a^(n - 2) = 0, so a^2 - a + 1 = 0 which has two complex roots (you can find them) which have modulus 1 and argument pi/3. So their powers 1, a, a^2, a^3, ... travel around the unit circle and come back to 1 after 2 pi/(pi/3) = 6 steps.

This analysis has the same defect as the corresponding one for differential equations -- how do you know to look for solutions of a certain kind? I don't have an answer for that, maybe someone else does. In the meantime, whenever you see a linear difference equation, think about solutions of the form a^n.

Solution 2

If applying your original formula for n-1

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

Than if I replace F(n-1) in the original F(n) expression

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

Since the later also is valid if I replace n with n-3

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

Combining the last two

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

Thus sequence is cyclical with the period of six

Comments

[Am_I_Helpful]

This is logical and apt explanation.

[Am_I_Helpful]

Very beautiful illustration,will upvote once my daily limit of 40 votes renew for tomorrow. :)

[Anup]

Thanks to your help I read from the below link. I don't know why substituting a^n for F[n], maybe because of some differential equation or maybe because recurrence relations increase at exponential rate or maybe trial. Now ignoring that fact we can find solution for the recurrence equation as you did here. I also observed that there are three numbers F[0], F[1], F[1]-F[0] and there negative (180 degree rotation) which are repeating. can u explain how the roots of this equation relate to actual solution link

[Anup]

I mean the solution of the equation give two roots which are 60 degree apart and are complex but how each one is related to each of the 6 values that are repeated.

[Robert Dodier]

@Grind Let a1, a2 be the roots. Then the solution is a linear combination F(n) = c1*a1^n + c2*a2^n. Given F0 = F(0) and F1 = F(1), you can find the constants c1, c2 by solving F0 = c1 + c2 and F1 = c1*a1 + c2*a2. When I do that, I get: c1 = (2*sqrt(3)*%i*F1 + (3-sqrt(3)*%i)*F0)/6, c2 = -(2*sqrt(3)*%i*F1 + (-sqrt(3)*%i-3)*F0)/6 (I'm working with Maxima). Then you can calculate F(2), F(3), F(4) from that. You'll find that the imaginary parts cancel out so the F(n) are real if F0 and F1 are real.

[sbabbi]

While this is 100% correct in theory, in practice these contests usually provide an input constraint such that the floating-point roundoff error would be too large to use this formula. There is a generic log(n) solution that uses matrix exponentiation and only integer arithmetic.

[Robert Dodier]

@sbabbi At least in this case, it's possible to work out the exact values of F(n) -- a computer algebra system (e.g. Maxima) helps. To do it by hand would be tedious, but not impossible. So round-off error doesn't come into play.