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$
  • 1
    $\begingroup$ Check documentation for RSolve. $\endgroup$ – Daniel Lichtblau Feb 10 '16 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 Feb 10 '16 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 Feb 10 '16 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$ – Daniel Lichtblau Feb 10 '16 at 21:48
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$
  • $\begingroup$ How can I get the expression? If not, this procedure shall restrict me to Mathematica itself. $\endgroup$ – Marvin Feb 10 '16 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$ – David G. Stork Feb 10 '16 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 Feb 10 '16 at 21:37
  • $\begingroup$ Gosh... so note even a simple upvote! $\endgroup$ – David G. Stork Feb 10 '16 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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