# How to find a recurrence relation for a sequence?

I have a sequence given by an explicit formula for n-th term:

seq[n_] := FullSimplify[LerchPhi[1/2, 2, -n] - 2^(-2-n) (π^2 - 6 Log^2)/3];
Array[seq, 10]
(* {1, 3/4, 35/72, 11/36, 347/1800, 149/1200, 9701/117600, 209/3675, 8093/198450, 6031/198450} *)


I am trying to find a recurrence relation for this sequence (e.g. in a form of DifferenceRoot object). An invocation of DifferenceRootReduce does not produce a desired result:

DifferenceRootReduce[LerchPhi[1/2, 2, -n] - 2^(-2-n) (π^2 - 6 Log^2)/3, n]
(* LerchPhi[1/2, 2, -n] - 2^(-2-n) (π^2 - 6 Log^2)/3 *)


Are there any other ways to find a recurrence relation for a sequence?

Using the identity:

$$\Phi (z,s,a)=\frac{\Phi (z,s,a-1)-\left((a-1)^2\right)^{-s/2}}{z}$$

First we define two recursive functions:

rGexp = -1/4 (Pi^2 - 6 Log^2)/3;
rGexp[n_] := 1/2 rGexp[n - 1]

rlp = LerchPhi[1/2, 2, 0];
rlp[n_] := 1/2 rlp[n + 1] + 1/(n)^2


rSeq[n_] := rlp[-n] + rGexp[n]

Simplify@Table[rSeq[n], {n, 1, 10}]

(* {1, 3/4, 35/72, 11/36, 347/1800, 149/1200, 9701/117600, 209/3675, 8093/198450} *)


Now, since

LerchPhi[1/2, 2, 0]
(* π^2/12 - Log^2/2 *)


The above can be reduced to (Thanks to @ybeltukov for noting it!):

f = 0
f[n_] := f[n - 1]/2 + 1/n^2
f /@ Range@9
(* {1, 3/4, 35/72, 11/36, 347/1800, 149/1200, 9701/117600, 209/3675, 8093/198450} *)

• I'd rather say that I found it by using Mathematics, not Mathematica. Anyway ... – Dr. belisarius Sep 3 '14 at 2:42
• belisarius, your result is quite simple: f = 0; f[n_] := f[n - 1]/2 + 1/n^2; :) May be you add it to the answer? – ybeltukov Sep 3 '14 at 6:50
• @ybeltukov: you're right. But how did you find this simple recurrence relation? We could formulate a modified problem as follows: given a numerical sequence of (say) rational numbers, is there (1) some "NDifferenceRootReduce" to find the recurrence relation or (2) a kind of "RFindFit" for a recurrence relation like f(n) = a f(n-1) + b(n), where a is a numerical parameter to be found and b(n) could be e.g. a polynomial with parameters to be found as well? – Dr. Wolfgang Hintze Sep 3 '14 at 11:34
• @Dr.WolfgangHintze I just looked at the belisarius's answer and saw that these two recurrence relations reduced to f[n_] := f[n - 1]/2 + 1/n^2. DifferenceRootReduce should find this formula, but LerchPhi is too difficult for it. For example, it works fine with Fibonacci[n] + n (see options here). – ybeltukov Sep 3 '14 at 11:51
• @Dr.WolfgangHintze It is interestiong, that Mathematica can do it in the opposite way. RSolve[{f[n] == f[n - 1]/2 + 1/n^2, f == 0}, f[n], n] gives an equivalent formula with LerchPhi. – ybeltukov Sep 3 '14 at 11:55