Recursion f(n) = f(n-1) + k*f(n)

In this forum members can discuss topics about specific programming languages.
Post Reply
Cerium
Posts: 8
Joined: Sun Oct 11, 2009 11:26 am

Recursion f(n) = f(n-1) + k*f(n)

Post by Cerium » Mon Oct 17, 2011 3:34 pm

Hello all,

First if this thread is misplaced I'm sorry I really don't know where to put it.

So here is my question, for some problems I have been able to "find" a way to solve them, but at some point I have something like:
f(n) = f(n-1) + k*f(n)
(with 0 < k < 1, and as n decrease, k decrease)

I imagine there's a mathematical way to find a result, but I don't know how. And well I would be more interested by a "computer" solution that I can code.

So if you have any idea of how to compute f(n) please share. And if there's no solution, please tell me :)

Thanks
Image

User avatar
jaap
Posts: 538
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Recursion f(n) = f(n-1) + k*f(n)

Post by jaap » Mon Oct 17, 2011 3:50 pm

Cerium wrote:f(n) = f(n-1) + k*f(n)
(with 0 < k < 1, and as n decrease, k decrease)
Just rewrite it as follows:
f(n) = f(n-1) + k*f(n)
f(n)-k*f(n) = f(n-1)
(1-k)f(n) = f(n-1)
f(n) = f(n-1)/(1-k)
and then it becomes easy to program. Even if k is not constant but some function of n, it still works.

Cerium
Posts: 8
Joined: Sun Oct 11, 2009 11:26 am

Re: Recursion f(n) = f(n-1) + k*f(n)

Post by Cerium » Mon Oct 17, 2011 4:08 pm

Oh yes obvious. I'm really feeling stupid right now. Thanks.
Image

Post Reply