# What function provides Recurrence relations?

Posted 1 month ago
304 Views
|
2 Replies
|
5 Total Likes
|
 WolframAlpha finds for some sequences Recurrence relations: The input of 2732,2728,1368,680,344,168,88,40,24,8,8,0,4 provides the Recurrence relation a(n+2)=a(n)/2-a(n+1)/2. The input of 5460,5464,2728,1368,680,344,168,88,40,24,8,8,0,4 provides the same Recurrence relation a(n+2)=a(n)/2-a(n+1)/2. 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?Thanks.
2 Replies
Sort By:
Posted 1 month ago
 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] Out[692]= DifferenceRoot[ Function[{\[FormalY], \[FormalN]}, {-\[FormalY][\[FormalN]] + \ \[FormalY][1 + \[FormalN]] + 2 \[FormalY][2 + \[FormalN]] == 0, \[FormalY][1] == 2732, \[FormalY][2] == 2728, \[FormalY][3] == 1368}]][n] 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} *) 
 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?