1
$\begingroup$

Is it possible to get symbolic expression for recursive function? In particular I am checking if a symbolic expression is possible (i.e. f[n]) for the following code:

f[x_] := If[x > 1, 2*f[x - 1] + 1, 1]
f[#] & /@ {1, 2, 3, 4, 5, 6, 7, 8, 9}

f[#] & /@ {1, 2, 3, 4, 5, 6, 7, 8, 9}

I tried using Nest[], but I suppose it is not applicable in this case, as it works for numeric depth.

$\endgroup$
4
  • 1
    $\begingroup$ Check documentation for RSolve. $\endgroup$ Commented Feb 10, 2016 at 21:19
  • $\begingroup$ @DanielLichtblau Could you post an answer so that I can accept? I used RSolve[f[n] - 2 f[n - 1] - 1 == 0, f[n], n][[1, 1]] /. C[1] -> 0 and got the expression. $\endgroup$
    – Marvin
    Commented Feb 10, 2016 at 21:35
  • $\begingroup$ no replacement rule is needed if you supply a boundary condition RSolveValue[{f[n] == 2 f[n - 1] + 1, f[1] == 1}, f[n], n] $\endgroup$
    – chuy
    Commented Feb 10, 2016 at 21:44
  • $\begingroup$ I put it in a community wiki response, but I'd not be surprised if the question gets closed anyway. $\endgroup$ Commented Feb 10, 2016 at 21:48

2 Answers 2

9
$\begingroup$

This sort of thing is handled by RSolve.

RSolve[{f[n] - 2 f[n - 1] - 1 == 0, f[1] == 1}, f[n], n]

(* Out[115]= {{f[n] -> -1 + 2^n}} *)
$\endgroup$
8
$\begingroup$
f[x_] := If[x > 1, 2*f[x - 1] + 1, 1];
f[#] & /@ {1, 2, 3, 4, 5, 6, 7, 8, 9}

(*

{1, 3, 7, 15, 31, 63, 127, 255, 511}

*)

FindSequenceFunction[{1, 3, 7, 15, 31, 63, 127, 255, 511}]

(*

-1 + 2^#1 &

*)

The above is the inferred expression uses all the information of the recursive definition and can be written $f(j) = -1 + 2^j$.

Check:

-1 + 2^#1 & /@ Range[9]

(*

{1, 3, 7, 15, 31, 63, 127, 255, 511}

*)

$\endgroup$
4
  • $\begingroup$ How can I get the expression? If not, this procedure shall restrict me to Mathematica itself. $\endgroup$
    – Marvin
    Commented Feb 10, 2016 at 21:10
  • $\begingroup$ The expression is given as the result: $f(j) = -1 + 2^j$ (where $j$ is the iteration number). What more could you ask for?! $\endgroup$ Commented Feb 10, 2016 at 21:22
  • $\begingroup$ I didn't get the significance of #1 in the beginning. Thanks for explaining. Although your answer is correct, I found using RSolve more elegant in mathematical sense as it uses information of the recursive function. $\endgroup$
    – Marvin
    Commented Feb 10, 2016 at 21:37
  • $\begingroup$ Gosh... so note even a simple upvote! $\endgroup$ Commented Feb 10, 2016 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.