# Can Mathematica solve this type of recurrence?

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.

• 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 :-) – Szabolcs Apr 10 '15 at 21:27
• You might make progress against this by using Guess by Manuel Kauers. – Mr.Wizard Apr 11 '15 at 17:30

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}]]


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.

• ListLogPlot[{Table[a[k], {k, 0, 15}], -Table[a[k], {k, 0, 15}]}, PlotStyle -> {Blue, Red}] – Dr. belisarius Apr 10 '15 at 21:47
• @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. – David G. Stork Apr 10 '15 at 21:53
• 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]. – Bob Hanlon Apr 10 '15 at 22:03
• 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. – Eleven-Eleven Apr 10 '15 at 22:41
• @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. – Szabolcs Apr 11 '15 at 16:47