The sequence below is Fibonacci sequence:
1, 1, 2, 5, 8, 13, 21, 35, ...
Fibonacci sequence has some characteristic that should be known. Let's say the th item of the sequence is , then:
We usually have or .
A convenient calculation of depends on following expressions:
This form represents items of Fibonacci sequence as the power of a matrix, so we can use Divide and Conquer to calculate in . Sepecifically, let's say we use to represent the matrix, if is even, can be gotten by:
Conversely, if is odd, we use .