# Reasoning about a recursive function

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?).

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