# Converting this recursive function into a non-recursive equation

I am trying to convert the following recursive function to a non-recursive equation:

$$f(n) = \begin{cases} 0,&\text{if n = 0;}\newline 2 \times f(n -1) + 1,&\text{otherwise.} \end{cases}$$

I have calculated the results for $n = 1$ through to $n = 6$ but I cannot find a discernible pattern from which to make an equation. The results are:

$$f(1) = 1$$

$$f(2) = 3$$

$$f(3) = 7$$

$$f(4) = 15$$

$$f(5) = 31$$

$$f(6) = 63$$

I hope I have formatted this correctly (my first time using LaTex), and if anyone could offer any help that would be greatly appreciated.

-
Find a recursion relation for the sequence (g(n)) of general term g(n)=f(n)+1. –  Did Aug 7 '11 at 17:54
Since $f(n+1)-f(n) = f(n)+1$ is not constant, $f(n)$ cannot be a linear function of $n$; if it were, then this difference would be constant. –  Arturo Magidin Aug 7 '11 at 17:55
I'm not sure what you mean by "linear equation," but if you merely add $1$ to every term in the sequence you'll see what the pattern is hopefully. –  anon Aug 7 '11 at 17:56
@Arturo: Perhaps my terminology isn't correct. A similar thing turned into $n^2 + n^3$ - that is kinda what I am wanting get to. –  SaladinAkara Aug 7 '11 at 17:57
@Saladin: Then your terminology is definitely off. In this context, "linear function" means a function of the form $f(n) = an+b$, with $a$ and $b$ constants. What you want is a non-recursive formula. –  Arturo Magidin Aug 7 '11 at 17:59

Will you be satisfied with $f(n)=2^n-1$?

-
Thank you, that's exactly what I wanted! –  SaladinAkara Aug 7 '11 at 18:02

It suffices to see that $$f(n) - f(n-1) = (2f(n-1) +1) - (2f(n-2) +1) = 2(f(n-1) - f(n-2)),$$ which proves, by induction, that $f(n) - f(n-1) = 2^{n-1}$, because $f(1) - f(0) = 1$. Using this, one can easily prove that $f(n) = 2^n - 1$.

Hope that helps,

-
Yes it does, thank you. –  SaladinAkara Aug 7 '11 at 18:05
RecursiveFunction(int n) {
if (n <= 0)
return 0;

return 2 * RecursiveFunction(n - 1) + 1;
}

Function(int n) {
int m;

for (m = 0; n > 0; n -= 1) {
m = 2 * m + 1;
}

return m;
}

-
-1: the question is not asking for an implementation in a programming language. –  Rahul Jul 2 '12 at 20:50