# How to find a recurrence relation for a numerical sequence?

This question was inspired by Vladimir Reshetnikov's question (How to find a recurrence relation for a sequence?):

Given a finite sequence of numbers, how can we find in MMA a recurrence relation obeyed by this sequence? To be more specific, assume that the numbers are rationals and the recurrence relation is of a simple type, say linear.

This problem is similar to FindFit for the function "behind" the sequence but now we are interested in a recurrence relation of a given form containing some Parameters.

Also there is a similarity to DifferenceRootReduce where MMA tries to find the recurrence relation for a given formula for the elements of a sequence. Now the formula is replaced by the numerical sequence. As an Option we would specify a class of recurrence relation, e.g. linear.

Let's consider the example of Vladimir, and take this sequnce

seq = Table[{n, -2^-n (2^(1 + n) LerchPhi[2, 2, 1 + n] - PolyLog[2, 2])}, {n, 1, 20}] // Simplify


$\left\{\{1,1\},\left\{2,\frac{3}{4}\right\},\left\{3,\frac{35}{72}\right\},\left\{4,\frac{11}{36}\right\},\left\{5,\frac{347}{1800}\right\},\left\{6,\frac{149}{1200}\right\},\left\{7,\frac{9701}{117600}\right\},\left\{8,\frac{209}{3675}\right\},\left\{9,\frac{8093}{198450}\right\},\left\{10,\frac{6031}{198450}\right\},\left\{11,\frac{1126651}{48024900}\right\},\left\{12,\frac{3587327}{192099600}\right\},\left\{13,\frac{990457463}{64929664800}\right\},\left\{14,\frac{1653005063}{129859329600}\right\},\left\{15,\frac{561462043}{51943731840}\right\},\left\{16,\frac{3778408}{405810405}\right\},\left\{17,\frac{951790361}{117279207045}\right\},\left\{18,\frac{1117157389}{156372276060}\right\},\left\{19,\frac{716038369549}{112900783315320}\right\},\left\{20,\frac{1600677857657}{282251958288300}\right\}\right\}$

Now let make an "educated guess" and assume a recurrence relation of the form

$f(n) = a f(n-1) + \frac{b}{n^2}$

How do we determine the two parameters $a$ and $b$? (In this example the solution is well known: $a = \frac{1}{2}$, $b=1$)

I tried to first RSolve the recurrence relation and then use FindFit to determine the parameters. It didn't work, too many error message and no result. Can you do better?

• Look at the documentation for FindLinearRecurrence – Bob Hanlon Sep 3 '14 at 12:50
• @Bob Hanlon: thank you for the hint. FindLinearRecurrence should solve the problem. But in fact, in this case it doesn't. – Dr. Wolfgang Hintze Sep 3 '14 at 13:07
• @Bob Hanlon: BTW, FindSequenceFunction is successful in this example. This is fine, but we want the recurrence relation. – Dr. Wolfgang Hintze Sep 3 '14 at 13:18
• stating the somewhat obvious but if you know the form you can find the coefficients from any pair of values: Solve[{3/4 == a 1 + b/(2^2), 35/72 == a 3/4 + b/3^2 }, {a, b}] => {{a -> 1/2, b -> 1}} – george2079 Sep 3 '14 at 20:52
• @george: of course, but I wanted to use MMA's inventory, as described in my answer. And this failed. So it's a statement on MMA. – Dr. Wolfgang Hintze Sep 4 '14 at 7:02

## 2 Answers

Once you have several consecutive triples {f[n-1],f[n],1/n^2}, the coefficients can be found by a NullSpace computation.

seq = ExpandAll[
FunctionExpand[
Table[-2^-n (2^(1 + n) LerchPhi[2, 2, 1 + n] - PolyLog[2, 2]), {n,
1, 20}]]];

n = 2;
tuples = MapIndexed[Join[#1, {1/(#2[[1]] + 1)^2}] &,
Partition[seq, n, 1]]

(* Out[563]= {{1, 3/4, 1/4}, {3/4, 35/72, 1/9}, {35/72, 11/36, 1/
16}, {11/36, 347/1800, 1/25}, {347/1800, 149/1200, 1/36}, {149/1200,
9701/117600, 1/49}, {9701/117600, 209/3675, 1/64}, {209/3675, 8093/
198450, 1/81}, {8093/198450, 6031/198450, 1/100}, {6031/198450,
1126651/48024900, 1/121}, {1126651/48024900, 3587327/192099600, 1/
144}, {3587327/192099600, 990457463/64929664800, 1/169}, {990457463/
64929664800, 1653005063/129859329600, 1/196}, {1653005063/
129859329600, 561462043/51943731840, 1/225}, In[564]:= {561462043/51943731840,
3778408/405810405, 1/256}, {3778408/405810405, 951790361/
117279207045, 1/289}, {951790361/117279207045, 1117157389/
156372276060, 1/324}, {1117157389/156372276060, 716038369549/
112900783315320, 1/361}, {716038369549/112900783315320,
1600677857657/282251958288300, 1/400}} *)

NullSpace[tuples]

(* Out[564]= {{1/2, -1, 1}} *)


The rest may be obvious to many readers, but to spell it out: the annihilator of the triple is {1/2,-1,1}, that is to say, the linear relation is {1/2,-1,1}.{f[n-1],f[n],1/n^2}==0.

seq = Table[-2^-n (2^(1 + n) LerchPhi[2, 2, 1 + n] -
PolyLog[2, 2]), {n, 25}] // Simplify;

seqFunc[n_] = FindSequenceFunction[seq][n] // Simplify


-2 LerchPhi[2, 2, 1 + n] + 2^-n PolyLog[2, 2]

seqFunc2[n_] = (a/c)*seqFunc[n - 1] + (b/d)/n^2 // Simplify;

recur = {f[n] == (a/c) f[n - 1] + (b/d)/n^2, f[1] == seqFunc[1]} /.
Simplify[
Solve[
Table[
seqFunc[n] == seqFunc2[n],
{n, 4}] //
Simplify,
{a, b, c, d}, Integers][[1]],
{Element[{a, b, c, d}, Integers],
a != 0, b != 0}] //
Quiet


{f[n] == 1/n^2 + 1/2 f[-1 + n], f[1] == 1}

RSolve[recur, f[n], n] // Simplify


{{f[n] -> -2 LerchPhi[2, 2, 1 + n] + 2^-n PolyLog[2, 2]}}