# 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 := a = 1
a := a = -1
a := a = 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 :-) Apr 10, 2015 at 21:27
• You might make progress against this by using Guess by Manuel Kauers. Apr 11, 2015 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 := 1;
a := -1;
a := 3;

a


(* $-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}] Apr 10, 2015 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. Apr 10, 2015 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, a, and a. Apr 10, 2015 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. Apr 10, 2015 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. Apr 11, 2015 at 16:47