Group Abstract

Message Boards

WOLFRAM COMMUNITY

2.7K Views

2 Replies

5 Total Likes

View groups...

Follow this post

Share this post:

GROUPS:

Wolfram Language

What function provides Recurrence relations?

Uwe Galle

Posted 7 years ago

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.

POSTED BY: Uwe Galle

2 Replies

Sort By:

Daniel Lichtblau

Daniel Lichtblau, Wolfram Research

Posted 7 years 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} *)

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} *)

POSTED BY: Daniel Lichtblau

Uwe Galle

Posted 7 years 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?

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?

POSTED BY: Uwe Galle

Reply to this discussion

Reply Preview

Attachments

Remove Add a file to this post

Follow this discussion

or Discard

Feedback