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,676

Hi

Supposing we have:

Supposing we wished to know what a was in:

We could form a recurrence, we could expand out g(x) with a computer,

we could get the Taylor series of a few terms of g(x) and hope to spot a pattern.

Or we could try to get an asymptotic expression for the coefficients of a. Here is

how to do it with the help of a CAS.

Start by getting the Laurent expansion for g(x):

Now we expand L(x) around 0.

Substitute x = 1 to form a sequence.

Fit a function to the above values. In this case a 4th degree polynomial was tried and found to be okay.

Now we have an asymptotic form for the coefficients of g(x)!

Plug in 1000000

That should be a very good approximation to the exact answer

**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,

Good one!

Have you tried to find the exact value?

"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,676

Hi gAr;

No, do you need it?

**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,

No, I was trying to compute, just to compare.

"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,676

Hi gAr;

I will try to get at least an accurate answer using another method.

**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,

Found that to be:

Close to your approximation, so I hope it's correct.

"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,676

Hi gAr;

You used the Knuth idea to get a smaller recurrence, very good. I am working

on a method that uses residues, it will take a while.

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,

Yes, I followed what the wise man said.

Okay, I'll wait.

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

Offline

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

Hi gAr;

Both residue methods failed. I do not have any other methods other than the two

up there.

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,

Okay.

But what is the residue method? Will that yield exact value?

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

Offline

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

Hi gAr;

Yes! But it is slowwwwww! If you want the coefficient

of x^100, you find the residue of g(x) / 101 at x = 0.

It is fast for small numbers but slows down for 1000001

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,

Hmmm, finding residues also involves expansion, isn't it? It's just as bad as expansion!

Knuth's method is the best bet for now!

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

Offline

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

Hi gAr;

I did not mean to expand them. The residues are computed by an integral

and a limit. Also Sage should have a residue command.

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,

I thought that residues are calculated by CAS by Laurent's series, I don't know!

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

Offline

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

Hi gAr;

Maybe, they have a definite integral over here but I can not get that

to work either.

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,

Can you put that integral here?

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

Offline

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

Hi gAr;

I will try, they have another idea that I am not following at all.

Please give me some time.

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, no problem.

Take your time!

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

Offline

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

Hi gAr;

I see what went wrong, the method is not for that rational type of generating function

it is for another type. In other words g(x) is not the correct form.

It also requires a numerical integration?

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,

Okay, you mean the other idea or the one you were trying earlier?

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

Offline

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

Hi;

The residue idea should work for g(x) and I tested up to say x^10000

where it got exact answers. I just used Mathematica's built in

residue command. Residue[ g(x) / x^10001, {x, 0}]

The other idea uses an integral it too gets exact answers, I have tried on small problems

but not for rational forms like g(x). At least I do not know to use it.

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,

Okay.

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

Offline

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

Hi gAr;

Here is an example of it working:

You need the coefficient of x^10

Which is correct without the i.

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,

I think a CAS would still need to expand it in order to integrate?

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

Offline

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

Hi;

Not if you numerically integrate it!

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

Combinatorics is Algebra and Algebra is Combinatorics.

Offline