3
$\begingroup$

I have the following recursively defined equation:

 a[n_] := a[n] =  1 - Sum[Binomial[n, k] 2^(n - k - 1) a[k], {k, 0, n - 2}] -  2 n*a[n - 1]
 a[0] := a[0] = 1
 a[1] := a[1] = -1
 a[2] := a[2] = 3

I want to solve this particular recurrence equation using RSolve, but I'm not sure that Mathematica can handle recurrences of this type, based upon the particular outputs I'm getting. Is there a way solve this type of recurrence using Mathematica?

I am looking for a closed form solution rather than computing a numerically.

$\endgroup$
  • $\begingroup$ I don't think RSolve can handle a recursion where $a_n$ is given as a function of all $a_k$ for $0\le k < n$ ... but I never dare say a categorical no :-) $\endgroup$ – Szabolcs Apr 10 '15 at 21:27
  • $\begingroup$ You might make progress against this by using Guess by Manuel Kauers. $\endgroup$ – Mr.Wizard Apr 11 '15 at 17:30
3
$\begingroup$

One can certainly compute a[n] for arbitrary positive integer $n$.

a[n_] := 1 - Sum[Binomial[n, k] 2^(n - k - 1) a[k], {k, 0, n - 2}] - 2 n a[n - 1];
a[0] := 1;
a[1] := -1;
a[2] := 3;

a[15]

(* $-694475294514315$ *)

 ListLogPlot[Table[a[i], {i, 1, 20}]]

enter image description here

Just note that many values of a[i] are negative and won't show up on the ListLogPlot.

However, attempts with FindSequenceFunction[] and FindGeneratingFunction[], even with appropriate FunctionSpace restrictions failed:

FindSequenceFunction[Table[{n, a[n]}, {n, 0, 20}],
FunctionSpace -> {"ConstantRecursive", "Hypergeometric"}]

I think the difficulty lies in the parametric nature of the sum's limits.

$\endgroup$
  • $\begingroup$ ListLogPlot[{Table[a[k], {k, 0, 15}], -Table[a[k], {k, 0, 15}]}, PlotStyle -> {Blue, Red}] $\endgroup$ – Dr. belisarius Apr 10 '15 at 21:47
  • $\begingroup$ @belisarius That computes twice as many points as necessary (quite a penalty for large lists), but shows the results. Simple interleaving (Riffle) of the even and odd values can fix that. $\endgroup$ – David G. Stork Apr 10 '15 at 21:53
  • $\begingroup$ Use of memorization ( a[n_] := a[n] = ... ) as shown in the original post would improve the efficiency. Although memorization and use of SetDelayed is not needed for the starting values of a[0], a[1], and a[2]. $\endgroup$ – Bob Hanlon Apr 10 '15 at 22:03
  • 2
    $\begingroup$ I appreciate the help. I'm looking for a closed form for the a[n]. Looking at a log table helps to see what appears to be some linearity here so I'm confident we can find something. $\endgroup$ – Eleven-Eleven Apr 10 '15 at 22:41
  • 1
    $\begingroup$ @Eleven-Eleven It's best to make this very clear in the question, especially after people have misunderstood it once (a bit of redundancy helps). I made the edit for you. $\endgroup$ – Szabolcs Apr 11 '15 at 16:47

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.