Message Boards Message Boards

0
|
1729 Views
|
6 Replies
|
3 Total Likes
View groups...
Share
Share this post:

Polynomial fit for recursion

Posted 1 year ago

If I'm not posting this in the correct place, someone, please tell me where to post it.

I have a linear recursion: f(n + 2) = (1/n) + (1 + 1/n) f(n), that I am trying to estimate the behavior of for large values of n. The solution is hideous (which is why I'm using Mathematica), and I don't know if I'm using the right tool.

I solved the recursion using RSolve. Then I tried to use Series[(...),{n, Infinity, 2}] to get the large n behavior, but the program flatly refused to do it. I fiddled with it for a while but couldn't get anywhere. Too complicated, I suspect. Is there another tool I can approach this with?

(I can, of course, just calculate the series and do a polynomial fit, but I'm trying to find a way to generate the solution from the recursion itself.)

Thanks! -Dan

POSTED BY: Daniel Boyce
6 Replies
Posted 1 year ago

Well, thanks for the tip. My copy of Mathematica doesn't have that. (It's rather old.) I'll have to work on it with RSolve and Series.

Thanks again for the help!

-Dan

POSTED BY: Daniel Boyce

There is a free tier of the Wolfram Cloud, in case you want to try the current version of the software.

As for even vs odd, this becomes computationally easier if you make it first order instead of second, and then after the fact change n to 2*n or 2*n+1 as appropriate.

POSTED BY: Daniel Lichtblau
Posted 1 year ago

Actually, there's only one condition as n is either even or odd, but I didn't tell you that part. :)

Okay. That's a new tool on me. I'll give that a try. Thank you!

-Dan

POSTED BY: Daniel Boyce

What are the initial conditions? Two are needed since this is a second order recurrence. If `f[1]==f[2]==1 for example, one might do as follows.

In[160]:= AsymptoticRSolveValue[{f[n + 2] == 1/n + (1 + 1/n)*f[n], 
  f[2] == 1, f[1] == 1}, f[n], n -> Infinity]

Out[160]= -1 - 1/2 E^(2 I n \[Pi]) + 
 E^(2 I n \[Pi]) (1/2 - 5/(4 n)) + 1/(4 n) + E^(2 I n \[Pi])/n + 
 Sqrt[n] (Sqrt[2/\[Pi]] + Sqrt[\[Pi]/2]) + 
 E^(I n \[Pi]) (Sqrt[\[Pi]/2]/(4 Sqrt[n]) - 
    Sqrt[n] Sqrt[\[Pi]/2]) + (-6 Sqrt[2] - 3 Sqrt[2] \[Pi])/(
 24 Sqrt[n] Sqrt[\[Pi]]) + 
 E^(I n \[Pi]) (Sqrt[n] Sqrt[2/\[Pi]] - 1/(2 Sqrt[n] Sqrt[2 \[Pi]]))

Similar can be achieved using RSolve and Series though with more work.

POSTED BY: Daniel Lichtblau
Posted 1 year ago

Umm... Okay, let's do this. The formula that RSolve gave is not very "tight" as far as a good solution is written. It spans about 30 lines. I solved the problem on paper, and though I haven't fully checked the work the expression is giving me the same problem.

Here is a term in the expression:

Product[(Product[2 k - 1, {k, 1, j - 1}]/Product[2 k, {k, 1, j - 1}])^2, {j, 1, n - 1}]

When I try to expand this for large n using Series:

Series[Product[(Product[2 k - 1, {k, 1, j - 1}]/Product[2 k, {k, 1, j - 1}])^2, {j, 1, n - 1}], {n, ∞, 2}]

it simply won't perform the calculation. Again, I'm not faulting the program, I'm asking it to do a rather hard job. I am wondering if there might be a better tool to use for this or if the built in Mathematica tools aren't set up for something like this.

Thanks!
-Dan

POSTED BY: Daniel Boyce

Welcome to Wolfram Community!
Please Edit your post and provide your trials in terms of Wolfram Language code. This will make it easier for other members to help you.

Check several methods available to include your code in the rules http://wolfr.am/READ-1ST

POSTED BY: Moderation Team
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract