Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
1  
Look at the documentation for FindLinearRecurrence –  Bob Hanlon Sep 3 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 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 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 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 at 7:02

2 Answers 2

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.

share|improve this answer
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]}}

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.