You are not logged in.
- Index
- » Computer Math
- » Generating recurrences from generating functions.
Post a reply
Topic review (newest first)
- bobbym
- 2011-05-06 15:03:58
They are pretty tough. It is a big field all by itself. I can do a little bit of it.
- gAr
- 2011-05-06 14:07:41
Yes, I have used. I actually wanted to say I never derived any.
- bobbym
- 2011-05-06 13:55:10
I will bet you have. Ever used Stirlings formula or the Hardy-Ramanujan formula?
An asymptotic form is as simple to use as an exact formula. The larger the number you need the more accurate they get.
- gAr
- 2011-05-06 13:33:57
Okay, but I have never used an asymptotic approximations.
- bobbym
- 2011-05-06 13:19:47
Even better at times is an asymptotic answer. These require a bit more math but save a ton of computation.
- gAr
- 2011-05-06 13:10:51
Yes, that's true!
It's useful for some counting problems.
- bobbym
- 2011-05-06 13:01:42
The method is useful at times. Sometimes even a package has trouble getting them. For instance:
If you needed something like the coefficient of x^224 519, a recursion is convenient.
Using expand is package abuse.
- gAr
- 2011-05-06 12:53:41
Hi bobbym,
Sometimes brain plays tricks on us. Forgets incidents which took place, creates memory of incidents that never happened etc.! I too have experienced it.
Anyway, I found the method to be cool.
And the pattern you have mentioned is easy to remember.
- bobbym
- 2011-05-06 12:30:13
Hi gAr;
That's it! I guess I did not invent it. Just rediscovered it. Or maybe I read about it over there, forgot about it and then thought it was my idea.
Thanks!
- gAr
- 2011-05-06 04:26:10
Hi bobbym,
The x d/dx log method is mentioned in generatingfunctionology.
- gAr
- 2011-05-05 19:42:30
Okay, I'll remember.
- bobbym
- 2011-05-05 19:23:45
Hi gAr;
A few caveats, for missing powers of x, just leave out the corresponding a(n)'s. Remember for finite k, that the actual expansion and the recursion will only agree for half the terms.
A sequence does not have to have a unique recurrence. There could shorter ones found by other methods.
- gAr
- 2011-05-05 19:18:48
Hi bobbym,
Thank you!
- bobbym
- 2011-05-05 18:01:38
Hi
I used to have a method called the x dx log(x) method. It would allow the changing of a generating function of the type:
Into a recurrence. One that would allow us to find the coefficients without expanding. The act of taking the log of g(x) and then differentiating it would result in linearizing the gf.
I can no longer remember what my method was but I do still have the program that does it for me. The next best thing is a general formula for this type problem.
Let us run a few test cases and in the best use of experimental math, see if we can spot a pattern. Proof comes later.
yields the recurrence:
yields the recurrence:
yields the recurrence:
yields the recurrence:
Seems like a pattern has developed.
yields the recurrence:
So doing the simple:
From the above formula:
Filling in for the variables: