Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
1  
Check documentation for RSolve. – Daniel Lichtblau Feb 10 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[1] -> 0 and got the expression. – Saurav Feb 10 at 21:35
    
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] – chuy Feb 10 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 at 21:48
up vote 9 down vote accepted

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}} *)
share|improve this answer
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}

*)

share|improve this answer
    
How can I get the expression? If not, this procedure shall restrict me to Mathematica itself. – Saurav Feb 10 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 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. – Saurav Feb 10 at 21:37
    
Gosh... so note even a simple upvote! – David G. Stork Feb 10 at 21:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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