$f(x) = f(x-1)*b \to f(x) = c_1 b^{x-1}$

Question

I'm trying to teach myself mathematics. I only started last year with a previous knowledge of basic arithmetic. I often make a detour into regions featuring problems that are a bit too deep for me. I'm often too curious to wait until I was able to catch up on the necessary bedding. I hope you'll excuse me :-)

Wolfram|Alpha says:

$$f(x) = f(x-1)*b \to f(x) = c_1 b^{x-1}$$

This is how I would compute the original recursive algorithm(?):

$$f(x) = f(x-1)*b$$

$$\begin{align} \\ f(4) &= f(4-1)*b \\ &= f(f(3-1)*b)*b \\ &= f(f(f(2-1)*b)*b)*b \\ &= f(f(f(f(1-1)*b)*b)*b)*b \\ &= \qquad ... \end{align}$$

But how do I compute the recurrence relation $f(x) = c_1 b^{x-1}$?

I would compute the Fibonacci numbers like this:

$$\begin{align} F_n &= F_{n-1} + F_{n-2}\\ F_0 &= 0\\ F_1 &= 1\\ F_5 &= F_{5-1} + F_{5-2}\\ &= F_4 + F_3\\ &= (F_3 + F_2) + (F_2 + F_1)\\ &= ((F_2 + F_1) + (F_1 + F_0)) + ((F_1 + F_0) + F_1)\\ &= (((F_1 + F_0) + F_1) + (F_1 + F_0)) + ((F_1 + F_0) + F_1) \\ &= 5 \end{align}$$

I'm also not sure about the difference between a recursive algorithm and its recurrence relation. I'd be grateful if someone could enlighten me or simply link me up.

Answer 1

I believe that your way to compute $f(n)$ is not correct, as you have outlined in the question. Observe that $f(4) = b * f(3) = b^2 * f(2)$ and not $f(4) = b * f(f(2)*b)$.

That said, you have $$f(n) = b * f(n-1) = b^2 * f(n-2) = \ldots = b^{n-1} * f(1).$$ Say that your initial condition states that $f(1) = c_1$, you can conclude that $f(n) = c_1 * b^{n-1}$.

Answer 2

A recurrence relation defines a function depending on its values on points of lower "rank". Since you want to be able to calculate the function, you also need some bases cases that are just given (like axioms). For example, the recurrence relation defining the Fibonacci numbers defines $F_n$ in terms of $F_{n-1},F_{n-2}$; the base cases $F_1=1,F_0=0$ are not defined in terms of previous elements.

We can have more complicated definitions of "rank". Here are two examples. One can define the binomial coefficients using Pascal's identity $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ with appropriate bases cases. Written out, that would be $$C(n,k) = C(n-1,k-1) + C(n-1,k), \quad C(0,k) = 1_{k=0}.$$ So in that cases $(n-1,\cdot)$ is of lower rank than $(n,\cdot)$.

Another example is the determinant - it's a function on $n \times n$ matrices (arrays of numbers) which is defined as the single value in case $n=1$, and using some formula involving $(n-1)\times(n-1)$ matrices otherwise.

In general, for the definition to work, the notation of rank must be a well ordering.

---

A recursive algorithm is a procedure which calls itself. For example, you can use the following pseudocode to calculate the Fibonacci numbers:

if ((n == 0) || (n==1)) return n;
else return F(n-1) + F(n-2);

Every recurrence relation can be computed this way. In this particular case, the algorithm for calculating $F_n$ runs in exponential time (in other words, it's very inefficient), and there are better ways to calculate $F_n$; for example, you could calculate the values iteratively:

F[0] = 0; F[1] = 1;
for (int i = 2; i <= n; i++) F[i] = F[i-1] + F[i-2];

There are even better algorithms.

Conversely, recursive algorithms have other uses, for example the best algorithms for sorting a list of numbers are recursive and use the "divide and conquer" paradigm.