existential theorem about Trigonometric Interpolation

Question

I have a problem with a theorem:

Theorem

---

For given numbers $y_{0}, \ldots, y_{n} \in \mathbb{C}$ and $x_{k} = k \frac{2 \pi}{n + 1} ( k = 0, \ldots, n)$ there exists exactly one function of the form $t_{n}^{*} = \sum\limits_{k = 0}^{n} c_{k} e^{ikx}$ with $t_{n}^{*}(x_{j}) = y_{j} (j = 0, \ldots, n)$.

The coefficients are determined by $c_{k} = \frac{1}{n + 1} \sum\limits_{j = 0}^{n} y_{j} e^{- i j x_{k}},\quad k = 0, \ldots, n$

---

I am trying to understand the proof of the theorem by myself. But I have problems to proof the equality

$t_{n}^{*}(x_{j}) = y_{j}\quad (j = 0, \ldots, n)$.

Thats my result until now:

$t_{n}^{*}(x_{k} )= \sum\limits_{k = 0}^{n} c_{k} e^{ikx_{k}} = \sum\limits_{k = 0}^{n} \left ( \frac{1}{n + 1} \sum\limits_{j = 0}^{n} y_{j} e^{- i j x_{k}} \right ) e^{ikx_{k}} $

$= \sum\limits_{k = 0}^{n} \left ( \frac{1}{n + 1} \sum\limits_{j = 0}^{n} y_{j} e^{- i j \frac{2 \pi k }{n + 1}} \right ) e^{ik \frac{2 \pi k }{n + 1}} = \sum\limits_{k = 0}^{n} \left ( \frac{1}{n + 1} \sum\limits_{j = 0}^{n} y_{j} e^{ - \frac{2 \pi k ij }{n + 1}} \right ) e^{ \frac{2 \pi k^{2} i }{n + 1}}$

$ = \sum\limits_{k = 0}^{n} \left ( \frac{1}{n + 1} \sum\limits_{j = 0}^{n} y_{j} e^{ \frac{2 \pi k^{2} i - 2 \pi k ij }{n + 1}} \right ) = \sum\limits_{k = 0}^{n} \left ( \frac{1}{n + 1} \sum\limits_{j = 0}^{n} y_{j} e^{ 2 \pi k i\frac{k - j }{n + 1}} \right )$

$ = \frac{1}{n + 1} \sum\limits_{k = 0}^{n} \sum\limits_{j = 0}^{n} y_{j} e^{ 2 \pi k i\frac{k - j }{n + 1}} $

But how I can continue ?

I would appreciate an answer.

Answer 1

Your error is in using $k$ twice, once in the index on the left side and then again as running index in the outer sum. These are different variables and should thus get a different name. If you repair that, the claim should quickly follow from the geometric sum formula.

In total this is called the Discrete Fourier Transform, DFT.

Answer 2

Thank you. Now I see my mistake.

I have now:

$t_{n}^{*}(x_{j} )= \sum\limits_{k = 0}^{n} c_{k} e^{ikx_{j}} = \sum\limits_{k = 0}^{n} \left ( \frac{1}{n + 1} \sum\limits_{j = 0}^{n} y_{j} e^{- i j x_{k}} \right ) e^{ikx_{j}} $

$= \sum\limits_{k = 0}^{n} \left ( \frac{1}{n + 1} \sum\limits_{j = 0}^{n} y_{j} e^{- i j \frac{2 \pi k }{n + 1}} \right ) e^{ik \frac{2 \pi j }{n + 1}} = \sum\limits_{k = 0}^{n} \left ( \frac{1}{n + 1} \sum\limits_{j = 0}^{n} y_{j} e^{ - \frac{2 \pi k ij }{n + 1}} \right ) e^{ \frac{2 \pi k i j }{n + 1}}$

$ = \sum\limits_{k = 0}^{n} \left ( \frac{1}{n + 1} \sum\limits_{j = 0}^{n} y_{j} e^{ \frac{2 \pi k i j - 2 \pi k ij }{n + 1}} \right ) = \sum\limits_{k = 0}^{n} \left ( \frac{1}{n + 1} \sum\limits_{j = 0}^{n} y_{j} \right )$

$ = \frac{1}{n + 1} \sum\limits_{k = 0}^{n} \sum\limits_{j = 0}^{n} y_{j} = \frac{1}{n + 1} \cdot (n + 1) \sum\limits_{j = 0}^{n} y_{j} = \sum\limits_{j = 0}^{n} y_{j} $

But I'm not finished. Sure I have another mistake, that I can't see.

Can you correct me ?

Good afternoon,

Tjay