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: