Message Boards Message Boards


What function provides Recurrence relations?

Posted 1 month ago
2 Replies
5 Total Likes

WolframAlpha finds for some sequences Recurrence relations:

The Guide Recurrence and Sum Functions is obviously intended as a comprehensive list of Recurrence and Sum Functions. But what function provides the result of WolframAlpha?

  • FindLinearRecurrence[{2732,2728,1368,680,344,168,88,40,24,8,8,0,4}] simlpy repeats the input in the output.
  • FindSequenceFunction[{2732,2728,1368,680,344,168,88,40,24,8,8,0,4},n] provides DifferenceRoot[Function[... . It's not a Recurrence relation.
  • FindGeneratingFunction[{2732,2728,1368,680,344,168,88,40,24,8,8,0,4},n] provides -((4 (1366+2047 n+683 n^2))/(-2-n+n^2)) . It's also not a Recurrence relation.

Is there no function what provides the Recurrence relation that WolframAlpha does provide or is the Guide Recurrence and Sum Functions simply incomplete?


2 Replies

I'm slightly surprised FindLinearRecurrence does not ahndle this. But it has been a while since I have seen anything in that code base. It might be done using FindSequenceFunction as in an example in the ref guide for DifferenceRoot under Properties & relations.

First get the DifferenceRoot solution.

ff = 
 FindSequenceFunction[{2732, 2728, 1368, 680, 344, 168, 88, 40, 24, 8,
    8, 0, 4}, n]

  Function[{\[FormalY], \[FormalN]}, {-\[FormalY][\[FormalN]] + \
\[FormalY][1 + \[FormalN]] + 2 \[FormalY][2 + \[FormalN]] == 
     0, \[FormalY][1] == 2732, \[FormalY][2] == 2728, \[FormalY][3] ==

Now recast as an explicit recurrence.

First[Head[ff]][a, n]

(* Out[694]= {-a[n] + a[1 + n] + 2 a[2 + n] == 0, a[1] == 2732, 
 a[2] == 2728, a[3] == 1368} *)
Posted 1 month ago

Thank you for this example. But this solution doesn't work in all cases:

 In[1]= ff=FindSequenceFunction[Table[Fibonacci[k], {k, 10}],n]
Out[1]= Fibonacci[n]
 In[2]= First[Head[ff]][a, n]

provides the error message

⋅⋅⋅ First: Nonatomic expression expected at position 1 in First[Fibonacci].
Out[2]= First[Fibonacci][a, n]

The same with Lucas numbers:

 In[3]= ff=FindSequenceFunction[Table[LucasL[k], {k, 10}],n]
Out[3]= LucasL[n]
 In[4]= First[Head[ff]][a, n]

provides the error message

⋅⋅⋅ First: Nonatomic expression expected at position 1 in First[LucasL].
Out[4]= First[LucasL][a, n]

Is there also a general solution?

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract