Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### allrounder's blog

By allrounder, history, 5 years ago, , 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  Comments (16)
 » 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 1row2 — 0 1 2/3 1row3 — 0 0 1 3/2row4 — 0 0 0 1On multiplying T and F the matrix you will get will have following states:row1 — f(n)row2 — (n+1)^2row3 — 3*(n+1)row4 — 2Consecutive multiplication will keep on yielding corresponding statesfor calculating f(k) just use T^(k-1)*F(n=1) for all k>=1.
 » 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 + 2vector = [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 * vectorthe result should be added sum(k*k) for 1 <= k <= NI guess there is a formula for that sum.
•  » » 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.
 » Recurrences of the form f n = f n - 1 + P k(n) have a solution of the form f n = P k + 1(n), as it's just a sum of the first n values of P k(n). In your case the solution is a cubic polynomial, you can find its coefficients by: guessing; use first 4 values of f n and solve a system of linear equalities; use formulas for sums like ; generating functions (but they are overkill there).
•  » » More recurrences can be easily solved using annihilators that allows to solve recurrences of the form f n = a 1 f n - 1 + a 2 f n - 2 + ... + a k f n - 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
•  » » @alexey.shchepin it was useful response
•  » » 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.
•  » » » 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.
•  » » » 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.
 » 5 years ago, # | ← Rev. 2 →   As (n + 1)2 = n 2 + 2n + 1, We can use 4 * 1 matrix with element F(n - 1), n 2, n, 1 and the translation matrix would be a 4 * 4 matrix with the following rows:1132012100110001
•  » » I have tried that method but it gives WA
 » 5 years ago, # | ← Rev. 3 →   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,...dOru 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
 » 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
•  » »
•  » » » 5 months ago, # ^ | ← Rev. 2 →   Thanks :)