Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

First of all, I am a computer science student, not a maths student. So maybe this is a trivial question, I just would like to understand it :)

Suppose I have the following (pointless) recursive function:

$$ f(x) = a + b \dot{} f(x) $$

for some constants a and b. I suppose that it does not really compute any values, or maybe maps its argument to $\pm\infty$ (except for the cases $b=0$ or $a = 0, b = 1$).

I would like to reason:

$$ f(x) - b \cdot f(x) = a \\ \vdots \\ f(x) = \frac{a}{1 - b} \\ $$

In terms of computation, this seems like a completely different function. So what is wrong about this reasoning (am I not allowed to treat the $=$ as equality? or $f(x)$ as a constant?).

share|improve this question
1  
It's the same function, it's just stated explicitly rather than implicitly. Also, this function is not recursive. Hint: $f(x+1)=a+b\cdot f(x)$ would be an example of a recursive recursive function. –  Ataraxia May 9 '13 at 20:53
    
You are observing that $x + b(x + b( x + b(\cdots))) = x + bx + b^2x + \cdots = x(1 + b + b^2 + \cdots) = \frac{x}{1 - b}$. This is a fixed point for your recursive formula. –  Sammy Black May 9 '13 at 21:03
    
Thank you for the response! Sorry, I actually removed that comment. The fact that $x(1 + b + b² \dots) = \frac{x}{1 - b}$ does not look really obvious though, does that equality have a name (or where could I find more info about)? –  Jacco May 9 '13 at 21:09
    
Yes, this fact has a name. In is known as the sum of the infinite geometric progression. There should not be nontrivial info about it. Its derivation is simple. Since, as can be seen directly, $(1–b)(1+b+\dots+b^n)=1–b^{n+1}$, we see that $(1+b+\dots+b^n)$ tends to $1/(1-b)$ when $n$ tends to $\infty$ (provided, of course, $|b|<1$). –  Alex Ravsky May 10 '13 at 2:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.