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
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
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 166 |
3 | adamant | 163 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Name |
---|
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.
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.
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 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:
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
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.
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
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
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
https://pastebin.com/embed_iframe/ZZ4kXFFe