How can I implement this more efficiently

Question

So I have a function (I'm writing this in a pseudo-functional language, I hope its clear):

dampen (lr : Num, x : Num) = x + lr*(1-x)

And I wish to apply this n times to a value x. I could implement it recursively:

dampenN (0, lr, x) = dampen(lr, x)
dampenN (n, lr, x) = dampenN(n-1, lr, dampen(x))

But there must be a way I can do it mathematically without resorting to an iterative procedure (recursive, or a loop).

Unfortunately my algebra skills are rusty beyond belief, can anyone help?

Answer 1

x + lr*(1-x) 
= x + lr - lr*x 
= x*(1-lr)+lr

applying it twice gives

(x*(1-lr)+lr)*(1-lr)+lr 
= x*(1-lr)^2 + lr*(1-lr) + lr

and three times

(x*(1-lr)+lr)*(1-lr)^2 + lr*(1-lr) + lr 
= x*(1-lr)^3 + lr*(1-lr)^2 + lr*(1-lr) + lr

or in general, n times gives

x*(1-lr)^n + lr * ( (1-lr)^n + (1-lr)^(n-1)...+(1-lr) +1)

Does that help?

Answer 2

We can eliminate the series from your formula entirely.

We are given:

x_(n+1) = x_n + lr(1-x_n)

This can be made simpler by rewriting as follows:

x_(n+1) = (1-lr)x_n + lr

Effectively, we've transformed this into tail recursion. (If you want the computer science perspective.)

This means that:

x_n = (1-lr)^n * x_0    +   ((1-lr)^(n-1) + (1-lr)^(n-2) + ... + 1)*lr 

The big term on the right is a geometric series, so that can be collapsed as well:

x_n = (1-lr)^n * x_0   +   lr *  (1 - (1-lr)^n) / (1- (1 -lr))
x_n = (1-lr)^n * x_0   +   1 - (1 - lr)^n

Edited due to a small error in the final expressions. +1 to comingstorm.