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.

  • 1
    Find a recursion relation for the sequence (g(n)) of general term g(n)=f(n)+1.2011-08-07
  • 0
    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.2011-08-07
  • 0
    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.2011-08-07
  • 0
    @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.2011-08-07
  • 0
    @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.2011-08-07
  • 0
    It seems *linear* refers to the function L such that g(n+1)=L(g(n)), in opposition to the *affine* function A such that f(n+1)A(f(n)).2011-08-07
  • 0
    @Arturo: Thanks for the clarification.2011-08-07

2 Answers 2

3

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

  • 0
    Thank you, that's exactly what I wanted!2011-08-07
  • 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 you.2011-08-07