In Matrix Exponentiation , how to solve this equation,

F(n) = a*F(n-1) + b*F(n-2) + c*F(n-3) + G(n)

G(n) = n*n*(n+1)

where max value of n can be 10^18

How to make the M matrix for such equations where the ‘n’ variable is present in the equations ?

In Matrix Exponentiation , how to solve this equation,

F(n) = a*F(n-1) + b*F(n-2) + c*F(n-3) + G(n)

G(n) = n*n*(n+1)

where max value of n can be 10^18

How to make the M matrix for such equations where the ‘n’ variable is present in the equations ?

2 Likes

hey thanks for your reply,

but i am confused that how to handle G(n)…

I had the same confusion 6 months ago ; all boils down to basic maths and manipulating your way to create a matrix which satisfies G(n) as well. To learn how to do that, read this:-

https://www.quora.com/How-do-I-simplify-a-recursion-equation-The-equation-is-f-n-2-n-3-f-n-3-f-n-1-We-are-given-the-values-f-0-f-1-f-2-Is-it-possible-to-get-an-expression-in-terms-of-n-for-f-n/answer/David-Smith-2412

After some basic maths for g(n),I have written a code. You can check here :- https://pastebin.com/v0z6uGru

1 Like

Hey!

I have gone through code. But, quite couldn’t understand why you took 12,10,8,6 and also why size to be 7?

Could you please explain or give any reference so that i can go through it and understand?

g(n) = n*n*(n+1),try to write g(n) = g(n-1) + something, that something will again in terms of n,let say d(n) again try doing this , u will get new equations , so total terms will 3 + 4(after expanding n*n*(n+1)= hence 7 terms.6,8,10,12 are base values of that equation.

1 Like

@maxwell_008 Thanks a lot. I understood it now

g(n) = n^{2} * (n+1) becomes g(n-1)+(3n^{2}- n)

considering d(n) = 3n^{2}- n, it can be written as d(n-1)+(6n-4)

considering m(n) as 6n-4, it can be written as m(n) = m(n-1)+6

substituting all, we get g(n) = g(n-1) + d(n-1) + m(n-1) + 6

=> g(n) = (n^{3}-2n^{2}+n)+(3n^{2}-7n+4)+(6n-10)+6

anyone??

That problem does not require matrix exponentiation at all, it has an O(1) solution, a simple formula which you have to derive, you can check the editorial in case deriving the formula gets hard

1 Like

Nice blog on Matrix Exponentiation by Zobayer Hasan :-

yeah i got the formula and struggled to get an AC but, the editorial said we can solve it using Matrix Exponentiation as well. So, that’s why i wanted to ask how to do it that way

@aarls

g(n) = g(n-1)+d(n-1)+m(n-1)+6

let n = 3

g(3) = g(2)+d(2)+m(2)+6

g(3) = (2^{2} * (2+1))+((3 * 2^{2})-2)+((6 * 2)-4)+6

g(3) = (4*3)+(12-2)+(12-4)+6

g(3) = 12+10+8+6

This is how you get base values as 12,10,8,6

this makes initial matrix as

f(2)

f(1)

f(0)

12

10

8

6

thanks bhai

So the answer in this case would be :

Product of matrix

{ a, b, c, 1, 1, 1 ,1

1, 0, 0, 0, 0, 0 ,0

0, 1, 0, 0, 0, 0 ,0

0, 0, 0, 12, 0, 0 ,0

0, 0, 0, 0, 10, 0 ,0

0, 0, 0, 0, 0, 8 ,0

0, 0, 0, 0, 0, 0 ,6 } (n-2) times multiplied by initial matrix which is

f(2)

f(1)

f(0)

12

10

8

6

@gpatel3

the Transformation matrix here would be

{ a,b,c,1,1,1,1

1,0,0,0,0,0,0

0,1,0,0,0,0,0

0,0,0,1,1,1,1

0,0,0,0,1,1,1

0,0,0,0,0,1,1

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

where as the initial matrix is

f(2)

f(1)

f(0)

12

10

8

6

So, the resultant becomes

f(3)

f(2)

f(1)

36

24

14

6

Because, we have expressed n^{2} * (n+1) as g(n), it becomes part of equation.

f(n) = a * f(n-1)+b * f(n-2)+c * f(n-3) + g(n)

Why this can’t be the transformation matrix :

{ a,b,c,1,1,1,1

1,0,0,0,0,0,0

0,1,0,0,0,0,0

0,0,0,1,0,0,0

0,0,0,0,1,0,0

0,0,0,0,0,1,0

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

@gpatel3 it would have been possible if the last 4 terms of initial matrix are constants. But, they are variables (dependent on value of n). That’s the reason the transformation matrix which you have mentioned can’t be used.