You are not logged in.
#1 2011-05-05 18:01:38
- bobbym
- Administrator
Online
Generating recurrences from generating functions.
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:
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#2 2011-05-05 19:18:48
- gAr
- Star Member
Offline
Re: Generating recurrences from generating functions.
Hi bobbym,
Thank you!
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
#3 2011-05-05 19:23:45
- bobbym
- Administrator
Online
Re: Generating recurrences from generating functions.
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.
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#4 2011-05-05 19:42:30
- gAr
- Star Member
Offline
Re: Generating recurrences from generating functions.
Okay, I'll remember.
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
#5 2011-05-06 04:26:10
- gAr
- Star Member
Offline
Re: Generating recurrences from generating functions.
Hi bobbym,
The x d/dx log method is mentioned in generatingfunctionology.
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
#6 2011-05-06 12:30:13
- bobbym
- Administrator
Online
Re: Generating recurrences from generating functions.
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!
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#7 2011-05-06 12:53:41
- gAr
- Star Member
Offline
Re: Generating recurrences from generating functions.
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.
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
#8 2011-05-06 13:01:42
- bobbym
- Administrator
Online
Re: Generating recurrences from generating functions.
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.
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#9 2011-05-06 13:10:51
- gAr
- Star Member
Offline
Re: Generating recurrences from generating functions.
Yes, that's true!
It's useful for some counting problems.
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
#10 2011-05-06 13:19:47
- bobbym
- Administrator
Online
Re: Generating recurrences from generating functions.
Even better at times is an asymptotic answer. These require a bit more math but save a ton of computation.
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#11 2011-05-06 13:33:57
- gAr
- Star Member
Offline
Re: Generating recurrences from generating functions.
Okay, but I have never used an asymptotic approximations.
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
#12 2011-05-06 13:55:10
- bobbym
- Administrator
Online
Re: Generating recurrences from generating functions.
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.
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#13 2011-05-06 14:07:41
- gAr
- Star Member
Offline
Re: Generating recurrences from generating functions.
Yes, I have used. I actually wanted to say I never derived any.
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
#14 2011-05-06 15:03:58
- bobbym
- Administrator
Online
Re: Generating recurrences from generating functions.
They are pretty tough. It is a big field all by itself. I can do a little bit of it.
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.