2
$\begingroup$

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.

  • 0
    @Arturo: Thanks for the clarification.2011-08-07

2 Answers 2

3

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

  • 1
    I have a problem similar to op, but not exactly equal... HOW you did that solution?2016-11-23
2

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,

  • 0
    Yes it does, thank $y$ou.2011-08-07