allrounder's blog

Recurrence using Matrix exponentiation
By allrounder, history, 9 years ago, In English

can anyone help me in solving the recurrence of the type f(n)=f(n-1) + n*n + 3*n + 2. i could not able to figure out how to solve this recurrence.....if there is any way out solve this would be helpful

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Make a 4*1 matrix F[][] as f(n-1) in row 1, n^2 in row 2, 3*n in row 3 and 2 in row 4.

Now you need a 4*4 transformation matrix T[][] that when multiplied by F[][] will yield a 4*1 matrix having states corresponding to n+1. This can be created as follows:

row1 — 1 1 1 1

row2 — 0 1 2/3 1

row3 — 0 0 1 3/2

row4 — 0 0 0 1

On multiplying T and F the matrix you will get will have following states:

row1 — f(n)

row2 — (n+1)^2

row3 — 3*(n+1)

row4 — 2

Consecutive multiplication will keep on yielding corresponding states

for calculating f(k) just use T^(k-1)*F(n=1) for all k>=1.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Note: I not sure if this is correct.

The trick is to split the formula in two parts.

let f(N) = f(N — 1) + 3N + 2

vector = [f(N), F(N — 1), N, 1]

matrix = [

[1, 3, 2, 0],

[0, 1, 0, 0],

[0, 0, 1, 1],

[0, 0, 0, 1]

]

compute matrix^N * vector

the result should be added sum(k*k) for 1 <= k <= N

I guess there is a formula for that sum.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't need to hold both f(N) and f(N-1) in your vector to solve this recurrence. I think there should be [1,0,3,2] in first row of your matrix instead of [1,3,2,0], and therefore, f(N-1) is useless.

    → Reply
»
9 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Recurrences of the form fn = fn - 1 + Pk(n) have a solution of the form fn = Pk + 1(n), as it's just a sum of the first n values of Pk(n). In your case the solution is a cubic polynomial, you can find its coefficients by:

  • guessing;
  • use first 4 values of fn and solve a system of linear equalities;
  • use formulas for sums like ;
  • generating functions (but they are overkill there).
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    More recurrences can be easily solved using annihilators that allows to solve recurrences of the form fn = a1fn - 1 + a2fn - 2 + ... + akfn - k + polynomial of n +  sum of exponential functions of n. In your special case, annihilators method simplify to your solution.

    You can find explanation of annihilators here: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3CC62D35F4710CB13B91F27051B4FCE9?doi=10.1.1.83.5012&rep=rep1&type=pdf

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey alexey.shchepin, How do you suggest to solve the following recurrence:

    f(n) = f(n-1) + (n-1)*f(n-2)

    I am not able to keep track of states in Matrix Exponentiation.Neither could I resolve it using some formula.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's non-linear, and matrix exponentiation approach is for linear recurrences, so it won't work here. If you really need a non-recurrent formula, then using exponential generating functions is the standard approach, but you won't get anything better than a linear time in your case, see OEIS. So it's simpler to directly use the recurrence if you need the exact result.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's your recurrence in OEIS: link. As you can see — no direct formula or smth else even in a simple case of a(0)=a(1)=1. I think, there is nothing better than a linear solution...

      There is one useful trick if your problem consists of different initial values. If you have f(1)=x, f(2)=y, then f(n)=a(n)*x+b(n)*y. Here a(n) and b(n) both satisfy the same equation as f(n), but have a(1)=1, a(2)=0 and b(1)=0, b(2)=1. So, you can first precompute a(n) and b(n), then answer f(n) for any initial f(1) and f(2) at constant time.

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

As (n + 1)2 = n2 + 2n + 1, We can use 4 * 1 matrix with element F(n - 1), n2, n, 1 and the translation matrix would be a 4 * 4 matrix with the following rows:

1132

0121

0011

0001

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

But i thought this is solvable with math and will get something like this : f(n) = a*n^3 + b*n^2 + c*n + d ,u can get several equation replacing them with initial value and solve them to get a,b,...d

Or

u can go something like this : f(n) will be 2*n + 3*(1+2+3+....+n) + (1^2+2^2+3^2+.....n^2) .replace with known series summation formula and solved

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to form transformation Matrix for f(n+1) = 36 f(n) + n (36^(n+1)) + 36^(n+1) + 36 relation ? Here in this case its {{36,36,36,1},{0,36,36,0},{0,0,36,0},{0,0,0,1}}. How it is formed ? Please explain it with example. problem link : https://www.codechef.com/problems/HLPMIL

→ Reply