How to solve this recurrence?

Question

I have a recurrence like this f(n)=(2*f(n-1)+2*f(n-2))%10007;

Now for a particular n i need to find:

g(n)=(f(n)f(0)+f(n-1)f(1)+....+f(0)f(n))%10007.

For example if n=3,

g(3)=(f(3)f(0)+f(2)f(1)+f(1)f(2)+f(0)f(3))%10007.

n can be as large as 10^9. I can find value of f(n) using matrix exponent in log(n) but i cant figure out how to get g(n).

(I need this to solve a problem from amritapuri 2008 regional

Answer 1

BACKGROUND

The original question is about how to tile a 2*n rectangle with 4 types of tiles.

What is unusual is that the tiling must divide into two pieces.

HINT 1

However, you can also consider this as a way of tiling this with the original 4 tiles coloured red, and another set of 4 tiles coloured blue such that the final board has a red side and a blue side.

HINT 2

Let f(n) be the number of ways of tiling a 2*n rectangle with just red tiles, and h(n) be the number of ways of tiling a 2*n rectangle with 0 or more columns of red tiles followed by 1 or more columns of blue tiles.

HINT 3

You can now find a simple matrix multiplication that gives the next values of h and f in terms of their two previous values and use the standard matrix power exponentiation to find the final values.

EXAMPLE CODE

Here is a Python demonstration that this formula gives the same answer as the original summation.

def f(n):
    """Number of ways to tile 2*n board with red tiles"""
    if n<0: return 0
    if n==0: return 1
    return 2*f(n-1)+2*f(n-2)

def g_orig(n):
    """Number of ways to tile 2*n board in two halves"""
    return sum(f(k)*f(n-k) for k in range(n+1))

def h(n):
    """Number of ways to tile 2*n board with red tiles and at least one column of blue tiles"""
    if n<1: return 0
    # Consider placing one column of blue tiles (either 2*1 or 2 1*1)
    t=2*(f(n-1)+h(n-1))
    # Also consider placing two columns of blue tiles (either a 2*2 or L shaped and a 1*1)
    t+=2*(f(n-2)+h(n-2))
    return t

def g(n):
    return f(n)+h(n)

for n in range(10):
    print n,g_orig(n),g(n)

Answer 2

Forget about 10007 for a second.

Let F(x)=sum(f(n)*x^n). Then F(x)=(f(0)+x*(f(1)-2f(0))/(1-2x-2x^2).

Let G(x)=sum(g(n)*x^n). Then G(x)=F(x)^2.

Thus the problem is reduced to finding the coefficient of a series (modulo 10007).

Answer 3

The trick is that the sequence f(n) mod 10007 has a period of 10007, i.e. f(n) mod 10007 = f(n + 10007) mod 10007. So all you need to do is simply (1) calculate f(0 .. n - 1) mod 10007, (2) calculate f(n - k)f(k) mod 10007 for 0 <= k < 10007, and then (3) sum them up according to your equation. You don't even need the power exponentiation method to calculate f(n).