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

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.

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!!!