A sparse string is a string consisting of only 0's and 1's with the constraint that it has no 2 1's consecutive.
Let A and B be two positive integers. The weight of a string is defined as A^{# 1's in the string} + B^{# 0's in the string}. Given an integer N, find the total weight of all sparse strings of length N.
Constraints : 1 ≤ A, B, N ≤ 1019.
PS: I figured out that number of sparse strings with z zeroes and o ones will be 
Also note that z ≥ ceil(N/2) and z ≤ N. So basically the problem reduces to finding
. I believe that the time complexity of the solution must be O(1)( a closed form solution of GN) or O(logn)(a recurrence relation for GN).
Can anybody provide a complete solution to the above problem?
I think the summation should start from ⌊ N / 2⌋. Anyway, it is related to Fibonacci polynomials, and there is a similar recurrence:
which can be calculated in $O(\log N)$.