Re: fibonacci -> FFT -> generating function?

On 7 Apr 2007 00:51:46 -0700, dillogimp@xxxxxxxxx wrote:

hi

Does FFT has the power to find the generating function for a
recursively generated sequence like fibonacci?

Well, FFT is an algorithm for numerical calculation of
(discrete) Fourier transforms, so _it_ doesn't have the
power to do anything remotely like this.

You could certainly say that the Fourier transform itself
has a lot to do with generating functions - if the
generating function for the sequence a_n is sum a_n z^n
then considering |z| = 1 gives you a Fourier series;
that Fourier series _is_ the Fourier transform of
the sequence a_n.


************************

David C. Ullrich
.

Relevant Pages

  • fibonacci -> FFT -> generating function?
    ... Does FFT has the power to find the generating function for a ... recursively generated sequence like fibonacci? ...
    (sci.math)
  • a probability density function & DWT
    ... for a sequence of with probability p, ... if we do Fourier transform, we have the generating function. ... So I am wondering that if we do DWT tranform of this sequence x, ...
    (sci.math)
  • Re: Zero-padding, resolution and aliasing
    ... sequence has an "actual" continuous spectrum ... Zero padding the time sequence and performing ... With the extra zeros it is then an infinite sequence. ... discrete-time Fourier transform. ...
    (comp.dsp)
  • Re: Numeric Sequence & Inverse Discrete Fourier Transform
    ... I had an idea for analyzing the sequence by applying a fourier ... For example, in the fourier transform, ... and tried to apply the inverse fourier transform. ... I can believe that the above "extrapolation" ...
    (comp.dsp)
  • Re: Zero-padding, resolution and aliasing
    ... discrete-time Fourier transform. ... So if we consider the two-sample sequence: ... an unspecified value is zero, ... saying that there is no such thing as a sequence ...
    (comp.dsp)