Re: fibonacci -> FFT -> generating function?
- From: "Keith Ramsay" <kramsay@xxxxxxx>
- Date: 7 Apr 2007 11:12:40 -0700
On Apr 7, 1:51 am, dillog...@xxxxxxxxx wrote:
|Does FFT has the power to find the generating function for a
|recursively generated sequence like fibonacci?
Well, what does the FFT of such a sequence look like? Suppose your
sequence is of the form,
f(k) = a1*b1^k + a2*b2^k + ... + ar*br^k,
where k=0,...,n-1. In the case of the Fibonacci sequence, r=2. In one
form the FFT is just
f^(j)
= sum{i=0,n-1} f(i)*e^(2*pi*i*j*k/n)
= sum{i=0,n-1} sum{s=1,k} as*bs^k*e^(2*pi*i*j*k/n)
= sum{s=1,k} as * sum{0,n-1} (bs*e^(2*pi*i*j/n))^k
= sum{s=1,k} as * ((bs*e^(2*pi*i*j/n))^n - 1)/(bs*e^(2*pi*i*j/n) - 1)
= sum{s=1,k} as * (bs^n - 1) / (bs*e^(2*pi*i*j/n) - 1).
You could try to figure out a1,b1, a2,b2, etc. from the result. In the
case of a sequence like Fibonacci, there's one term that's much bigger
than the others. The magnitude of that term is greatest at j=0 and
smallest when j is around n/2. The ratio might let you figure out what
b1 is.
But why go through the torture when you can more easily find the
generating function some other way?
Keith Ramsay
.
- References:
- fibonacci -> FFT -> generating function?
- From: dillogimp
- fibonacci -> FFT -> generating function?
- Prev by Date: Re: Cantor Confusion
- Next by Date: Hypotenuse Square Discovered.By Aiya-Oba
- Previous by thread: Re: fibonacci -> FFT -> generating function?
- Next by thread: Symlectic integration of variational equation
- Index(es):
Relevant Pages
|
