4
$\begingroup$

I am having an issue with the RSolveValue/RSolve function. Specifically, Mathematica is able to correctly evaluate RSolveValue[{f[0] == 1, f[n] == Sum[f[i], {i, 0, n - 1}]}, f[n], n] to Piecewise[{{Power[2, n - 1], n > 0}, {1, n == 0}}, 0], but fails if the indices of the summation are shifted by one: RSolveValue[{f[0] == 1, f[n] == Sum[f[i+1], {i, -1, n - 2}]}, f[n], n] does not evaluate, even though the two summations seem to be clearly equivalent. Is there some way to nudge Mathematica into realizing that these two recurrences are one and the same?

I should note that this issue arises while I am using Mathematica programmatically in Python to do analysis (though the issue is reproducible in the standard Mathematica application). As such, even though there is a case where RSolve is working, the symbolic math library that I am using sometimes produces the shifted indices, and I am hoping that it will be an easier fix to have Mathematica resolve the shifted summation rather than transform the symbolic Python expression.

My Mathematica installation is version 12.3.0.0. Thank you for any help!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$ 
$Version

(* "13.2.1 for Mac OS X ARM (64-bit) (January 27, 2023)" *)

ClearAll["Global`*"];

RSolveValue[{f[0] == 1, f[n] == Sum[f[i + 1], {i, -1, n - 2}]}, f[n], n]

enter image description here

If you cannot restructure the sum, use the recursive definitions to generate a sequence, then try using FindSequenceFunction to find the closed-form.

f2[0] = 1;
f2[n_Integer?Positive] := f2[n] = Sum[f2[i + 1], {i, -1, n - 2}]

f[n_Integer?NonNegative] = Piecewise[{
   {FindSequenceFunction[f2 /@ Range[6], n], n > 0}, {1, n == 0}}]

enter image description here

And @@ (f[#] == f2[#] & /@ Range[0, 20])

(* True *)
Improve this answer
$\endgroup$
1
  • $\begingroup$ It is an unfortunate weakness that this sort of trick would be needed. An advantage is that it will work if the recurrence is linear (as in the example) and if given sufficiently many terms. $\endgroup$
    – Daniel Lichtblau
    May 12 at 15:52
1
$\begingroup$

Would this work for you?

RSolveValue[{f[0] == 1, f[n] == 1 + Sum[f[i + 1], {i, 0, n - 2}]}, 
 f[n], n]
Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your response, but I more so am looking for any flags or assumptions to give Mathematica such that it directly evaluates RSolveValue[{f[0] == 1, f[n] == Sum[f[i+1], {i, -1, n - 2}]}, f[n], n]. While your code is another equivalent formulation that Mathematica is able to evaluate, it would require me to transform the original recurrence into the form in your answer, which leaves me in the same situation that I am in currently. $\endgroup$
    – B. Freeman
    Jun 25, 2021 at 19:18
  • $\begingroup$ This seems to be a deficiency in RSolve to me. Can you transform so that the initial index in the sum is the same as the first index in the first term? $\endgroup$
    – Craig Carter
    Jun 25, 2021 at 21:06
  • $\begingroup$ Yes, if this is truly a deficiency in RSolve, then I'll have to do some sort of preprocessing in my code along those lines. Hopefully, I can find a heuristic to normalize the summation such that Mathematica will accept it for all the recurrences I come across. $\endgroup$
    – B. Freeman
    Jun 25, 2021 at 22:11

Your Answer

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

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