# Fourier Transform (Numerical Analysis)

1. Sep 25, 2011

### Scootertaj

1. Calculate the finite Fourier transform of order m of the following sequences:

a) uk = 1, 0$\leq$k$\leq$N-1
b) uk = (-1)k, 0$\leq$k$\leq$N-1 N even
c) uk = k, 0$\leq$k$\leq$N-1

2. Relevant equations
Uk = (1/N)$\sum$uke-2pi*i*k*j/N from j=0 to N-1 ; 0<=k<=N-1

Attempt:
a) First thing that I tried is that $\sum$x^k = $\frac{1}{1-x}$ but that doesn't seem to get where I want. For example, I know that for a), we get 1 for k=0 and 0 for k$\neq$0 , but this would give 1/N (1) for k = 0 and I don't know what for any other k.
So, I found a formula that says:
$\sum$ei*k*j from j = 0 to N-1
={ 0 if e$\neq$1,
{ N-1 else.

b) wouldn't we get (1/N)$\sum$-e-2pi*i*k*j/N from j=0 to N-1 ; 0<=k<=N-1 which is the same as part a) ?
c) I think I need to use the idea that $\sum$k*x^k = $\frac{x}{(1-x)2}$

Obviously, if this formula is valid (I have no idea), then it would give 1 for 0 and 0 for other k for part a) which is correct

Any ideas?

Last edited: Sep 25, 2011
2. Sep 26, 2011

### Scootertaj

Just a bump

3. Sep 26, 2011

### Scootertaj

Nevermind I got it