# Symbolic expression for recursion

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.

• Check documentation for RSolve. – Daniel Lichtblau Feb 10 '16 at 21:19
• @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 -> 0 and got the expression. – Marvin Feb 10 '16 at 21:35
• no replacement rule is needed if you supply a boundary condition RSolveValue[{f[n] == 2 f[n - 1] + 1, f == 1}, f[n], n] – chuy Feb 10 '16 at 21:44
• I put it in a community wiki response, but I'd not be surprised if the question gets closed anyway. – Daniel Lichtblau Feb 10 '16 at 21:48

This sort of thing is handled by RSolve.

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

(* Out= {{f[n] -> -1 + 2^n}} *)

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


(*

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

*)

• How can I get the expression? If not, this procedure shall restrict me to Mathematica itself. – Marvin Feb 10 '16 at 21:10
• The expression is given as the result: $f(j) = -1 + 2^j$ (where $j$ is the iteration number). What more could you ask for?! – David G. Stork Feb 10 '16 at 21:22
• 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. – Marvin Feb 10 '16 at 21:37
• Gosh... so note even a simple upvote! – David G. Stork Feb 10 '16 at 21:44