Math Is Fun Forum

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

You are not logged in.

#1 2011-08-05 20:21:10

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#2 2011-08-05 20:44:26

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Getting an asymptotic form for a GF.

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

#3 2011-08-05 20:53:18

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#4 2011-08-05 20:57:07

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Getting an asymptotic form for a GF.

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

#5 2011-08-05 21:01:05

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#6 2011-08-05 21:24:12

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Getting an asymptotic form for a GF.

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

#7 2011-08-05 21:29:18

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#8 2011-08-05 21:35:39

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Getting an asymptotic form for a GF.

Hi,

Yes, I followed what the wise man said.
Okay, I'll wait.


"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

#9 2011-08-05 21:59:23

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#10 2011-08-05 22:03:11

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Getting an asymptotic form for a GF.

Hi bobbym,

Okay.
But what is the residue method? Will that yield 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

#11 2011-08-05 22:06:33

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#12 2011-08-05 22:11:58

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Getting an asymptotic form for a GF.

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!


"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

#13 2011-08-05 22:21:40

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#14 2011-08-05 22:35:43

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Getting an asymptotic form for a GF.

Hi bobbym,

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


"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

#15 2011-08-05 22:57:15

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#16 2011-08-05 22:59:48

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Getting an asymptotic form for a GF.

Hi bobbym,

Can you put that integral here?


"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

#17 2011-08-05 23:03:26

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#18 2011-08-05 23:06:15

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Getting an asymptotic form for a GF.

Okay, no problem.
Take your time!


"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

#19 2011-08-05 23:16:12

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#20 2011-08-05 23:36:09

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Getting an asymptotic form for a GF.

Hi bobbym,

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


"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

#21 2011-08-05 23:40:20

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#22 2011-08-05 23:46:20

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Getting an asymptotic form for a GF.

Hi bobbym,

Okay.


"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

#23 2011-08-05 23:57:27

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#24 2011-08-06 00:03:57

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: Getting an asymptotic form for a GF.

Hi bobbym,

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


"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

#25 2011-08-06 00:06:42

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Getting an asymptotic form for a GF.

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB