Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,388

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.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

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."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,388

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.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

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."

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

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."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,388

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.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

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.

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,388

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.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Yes, that's true!

It's useful for some counting problems.

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,388

Even better at times is an asymptotic answer. These require a bit more math but save a ton of computation.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Okay, but I have never used an asymptotic approximations.

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,388

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.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Yes, I have used. I actually wanted to say I never derived any.

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,388

They are pretty tough. It is a big field all by itself. I can do a little bit of it.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline