Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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

As pointed out in the comments, the issue you're running into is that your $f(x)$ isn't defined recursively. When one says "$f$ is defined recursively," they mean that the value of $f(x)$ is a function of values of $f$ at points other than $x$. For instance, the following are all recursive functions: \begin{align} f(x) &= a+b\cdot f(x-1),\quad x>0 \\ g(n) &= g(n-1) + g(n-2),\quad n\geq 2 \end{align} (Notice that we need to specify the values of $x$ where the recurrence is valid; we also need some initial conditions or boundary values, but that strays from your current question.)

However, your function $f(x)$ does not depend on prior values of $x$. Rather, you've really just described a constant function implicitly, rather than explicitly:

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

The equation on the far left is an implicit definition because you have defined $f(x)$ in terms of itself (not for values of $f(a),\;a\neq x$), while the equation on the right is a explicit definition.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.