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
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 18.04.2026 05:28:30 (n2).
Десктопная версия, переключиться на мобильную.
При поддержке
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