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

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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3567 |

3 | Um_nik | 3527 |

4 | ecnerwala | 3458 |

5 | maroonrk | 3409 |

6 | 300iq | 3317 |

7 | Petr | 3272 |

8 | LHiC | 3229 |

9 | Benq | 3226 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 197 |

2 | antontrygubO_o | 188 |

3 | pikmike | 183 |

4 | Ashishgup | 182 |

5 | vovuh | 179 |

6 | Radewoosh | 167 |

7 | Um_nik | 165 |

8 | tourist | 163 |

9 | McDic | 162 |

10 | Geothermal | 157 |

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

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/02/2020 10:21:03 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

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

f_{ n}=f_{ n - 1}+P_{ k}(n) have a solution of the formf_{ n}=P_{ k + 1}(n), as it's just a sum of the firstnvalues ofP_{ k}(n). In your case the solution is a cubic polynomial, you can find its coefficients by:f_{ n}and solve a system of linear equalities;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 ofn+ sum of exponential functions ofn. 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.

As (

n+ 1)^{2}=n^{2}+ 2n+ 1, We can use 4 * 1 matrix with elementF(n- 1),n^{2},n, 1 and the translation matrix would be a 4 * 4 matrix with the following rows:1132

0121

0011

0001

I have tried that method but it gives WA

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

Thanks :)

You can use this link for more about this kind of functions: https://codeforces.com/blog/entry/67776