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: 96,633

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

**If it ain't broke, fix it until it is.**

**Online**

**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: 96,633

Hi gAr;

No, do you need it?

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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: 96,633

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

**If it ain't broke, fix it until it is.**

**Online**

**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: 96,633

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.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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: 96,633

Hi gAr;

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

up there.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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: 96,633

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

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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: 96,633

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.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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: 96,633

Hi gAr;

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

to work either.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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: 96,633

Hi gAr;

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

Please give me some time.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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: 96,633

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?

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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: 96,633

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.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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: 96,633

Hi gAr;

Here is an example of it working:

You need the coefficient of x^10

Which is correct without the i.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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: 96,633

Hi;

Not if you numerically integrate it!

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**