Comment body goes here.
As you can see the recurrence we get in the solution is
rec(n) = rec(n-1) + rec(n-2)
Does this look familiar?
This is the fibonacci sequence.
One way we can solve the same is by using matrices as shown in the following equation
Now to solve for the power n in O(log n) time using binary exponentiation which gives us the desired O(log n) solution.
Use matrix exponentiation