How to solve linear homogenus difference equatation in logarithmic time

Linear homogeneous difference equation of degree k with constant coefficient is a form:

a[n]=c1a[n-1]+c2a[n-2]+c3a[n-3]+…+ck a[n-k];

where c1,c2,…,ck are real numbers and ck!=0

Solution of this type of equations can be find applying following steps:

Step 1:

Define k*1 dimensional vector A_k with entries { a[n],a[n-1],a[n-2],a[n-3],a[n-4],…,a[n-k+1] }

Step 2:

Define another k*1 dimensional vector A_k-1 with entries { a[n-1],a[n-2],a[n-3],a[n-4],…,a[n-k] }

Step 3:

Represent A_k = (T)*(A_k-1) Here T is a linear operator matrix of dimension k*k

and  ‘*’  is the symbol of matrix multiplication

we can define T as:

T={   {c1,c2,c3,c4,…,ck},

{1,0,0,0, …0}

{0,1,0,0, …0 },

{0,0,1,0, …0 },

{0,0,0,1, …0 },

……………….

……………….

{0,0,0,….,1,0}}

now you can define

A_k=(T^k)*(A_0)

T^k can be computed by recursive squaring procedure which is O(log(n))

so by applying these three steps you can get solution of any linear homogeneous equation  in O(log(n)) .

Here is one problem of code-star which has direct application of this :

Problem:

https://www.hackerrank.com/contests/codestar-long-programming-contest/challenges/alien-2

In this problem the important constrain is that is you can only put white flowers in the bunch of K=5

The no. of sequences which have first red flower are the same as solving this problem with parameter  n-1

because if you are putting red flower at first position then rest of n-1 positions are  independent.

The no. of sequences which have first white flower are the same as solving this problem with parameter  n-5

because if you are putting white flower at first position then you have to put white flowers up to 5th position after 5th position putting flowers on rest of the positions is independent.

so your solution for the parameter n is

ans(n)=no. of n length sequences which have follow the given constraint, therefore

ans(n)=ans(n-1)+ans(n-5);

which is linear homogeneous difference equation so you can find the solution by above three steps

then,

T={ {1,0,0,0,1},

{1,0,0,0,0}

{0,1,0,0,0}

{0,0,1,0,0}

{0,0,0,1,0}}

Java implementation of this problem:

https://ideone.com/fVParM