I'm looking for a good tutorial about matrix exponentiation, where explain how can i solve a recurrence like this: f(n)=f(n-1)+n*2
I know how to use matrix exponentiation to solve a recurrence where are used anterior terms, but i don't know when the recurrence have one term that depend to the position of the term.
thank you!!!
I think you meant f(N)=F(N-1)+2*n;
well that reccurence can be solved using a forumula (if you factor out the 2)
there is also a way to solve it using matrix exponentiantion:
Well as you know its hard (or atleast i dont know how) to solve when you have to add a different number every time , but what if you add a constant?
thats easier , that can be done , a function like f(x)=f(x-1) +Constant can be exponentiated if you want
lets reduce the original problem to one wich has only constant C's
For that , we have to keep track 2 variables , instead of one :
The position , & , The current value
now :
value[i]=value[i-1]+position[i-1]+2
position[i]=position[i-1]+2
see now ? now what i need to add its constant (its 2) and this type or recurennce is liniar , you can solve this by matrix exponential
Oh and if you wonder how to solve for the constant , here is my idea : keep a third variable wich is constant ! lol
TWO[i]=TWO[i-1]
value[i]=value[i-1]+position[i-1]+TWO[i-1]
position[i]=position[i-1]+TWO[i-1]
now youve got nothing to add
How is f(n) = f(n) + 2.n a valid recurrence? f(n) should depend on f(n - 1) or f(n - 2) or some other previous term but it cannot depend on itself.
I fixed the question, thank!!!
The recurrence you have written simply evaluates to n * (n + 1).
f(n) = f(n — 1) + 2 * n
= f(n — 2) + 2 * (n + (n — 1))
and so on.
Hence, f(n) = 2 * (1 + 2 + ... + n)
Also, any recurrence of the form of f(n) = f(n — 1) + p(n) can be solved in a similar way without matrix exponentiation.
Thank everybody, i understand now how to solve this kind of problem. And I share with all of you a page very interesting that i found.
This is the link.
So, the answer is to make enother function for keep the position, something like this:
My 1rt recurrences:
f(n)=f(n-1)+2*n
The part n (the position), can transform in another recurrence, like this:
g(n)=g(n-1)+1
(is ease to see).And for concluding make the matrix exponentiation:
|1 2 0| |f(n)|
|0 1 1|*|g(n)|=
|0 0 1| | 1 |
|f(n+1)|
|g(n+1)|
| 1 |
And this is all, i hope that help you!!!