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$
2
  • $\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, 2015 at 21:27
  • $\begingroup$ You might make progress against this by using Guess by Manuel Kauers. $\endgroup$
    – Mr.Wizard
    Apr 11, 2015 at 17:30

1 Answer 1

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$
5
  • $\begingroup$ ListLogPlot[{Table[a[k], {k, 0, 15}], -Table[a[k], {k, 0, 15}]}, PlotStyle -> {Blue, Red}] $\endgroup$ Apr 10, 2015 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$ Apr 10, 2015 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, 2015 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$ Apr 10, 2015 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, 2015 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.