5
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Look at the documentation for FindLinearRecurrence $\endgroup$
    – Bob Hanlon
    Sep 3, 2014 at 12:50
  • $\begingroup$ @Bob Hanlon: thank you for the hint. FindLinearRecurrence should solve the problem. But in fact, in this case it doesn't. $\endgroup$
    – Dr. Wolfgang Hintze
    Sep 3, 2014 at 13:07
  • $\begingroup$ @Bob Hanlon: BTW, FindSequenceFunction is successful in this example. This is fine, but we want the recurrence relation. $\endgroup$
    – Dr. Wolfgang Hintze
    Sep 3, 2014 at 13:18
  • $\begingroup$ 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}} $\endgroup$
    – george2079
    Sep 3, 2014 at 20:52
  • $\begingroup$ @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. $\endgroup$
    – Dr. Wolfgang Hintze
    Sep 4, 2014 at 7:02

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$ 
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]}}

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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