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

math sequence discrete-mathematics cyclic
Anup picture Anup · May 30, 2015 · Viewed 12.8k times · Source

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.

Answer

Igor Popov picture Igor Popov · May 30, 2015

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

Related questions

How can I check for NaN values?

float('nan') results in Nan (not a number). But how do I check for it? Should be very easy, but I cannot find it.

Read More
Math.random() explanation

This is a pretty simple Java (though probably applicable to all programming) question: Math.random() returns a number between zero and one. If I want to return an integer between zero and hundred, I would do: (int) Math.floor(Math.…

Read More
Calculate distance between two latitude-longitude points? (Haversine formula)

How do I calculate the distance between two points specified by latitude and longitude? For clarification, I'd like the distance in kilometers; the points use the WGS84 system and I'd like to understand the relative accuracies of the approaches available.

Read More