Where is the flaw in this derivation of the DTFT of the unit step sequence $u[n]$?

Question

This question is related to this other question of mine where I ask for derivations of the discrete-time Fourier transform (DTFT) of the unit step sequence $u[n]$. During my search for derivations I found one which is amazingly simple. I first saw it on page 138 of this book by B.A. Shenoi. I also came across it on mathematics.SE in this answer.

Since the argument is short and simple I will repeat it here for convenience.

The unit step sequence can be written as $$u[n]=f[n]+\frac12\tag{1}$$ with $$f[n]=\begin{cases}\frac12,\quad n\ge 0\\-\frac12,\quad n<0\end{cases}\tag{2}$$ Obviously, $$f[n]-f[n-1]=\delta[n]\tag{3}$$ Applying the DTFT on both sided of $(3)$ gives $$F(\omega)\left(1-e^{-j\omega}\right)=1\tag{4}$$ where $F(\omega)$ is the DTFT of $f[n]$. From $(4)$ we get $$F(\omega)=\frac{1}{1-e^{-j\omega}}\tag{5}$$ From $(5)$ and $(1)$ we get for the DTFT of $u[n]$ $$U(\omega)=F(\omega)+\pi\delta(\omega)=\frac{1}{1-e^{-j\omega}}+\pi\delta(\omega),\quad -\pi\le\omega <\pi\tag{6}$$ where I've used $\text{DTFT}\{1\}=2\pi\delta(\omega)$, $-\pi\le\omega <\pi$.

Eq. $(6)$ for the DTFT of $u[n]$ is no doubt correct. However, the derivation is flawed.

The question is: find and explain the flaw in above derivation.

Please prepend your answer with the spoiler tag >!.

Answer 1

There are infinitely many signals that make the following equality hold: $$y[n]-y[n-1]=\delta[n] \qquad (1)$$ The only thing that matters is that $y[0]-y[-1]=1$, and then the rest of the coefficients of $y$ can be determined under the restriction that Eq. $(1)$ states (i.e. the substraction of consecutive samples must be $0$ for $n\neq 0$). In other words, Eq. $(1)$ will be achieved by any signal $y[n]$ such that $$y[0]=y[-1]+1 \land y[n]=y[n-1] \ \forall n\neq0$$ Another way to see this is that any function that is basically $u[n]$ with an offset (a constant value added) will satisfy $(1)$. This explains the statement made by robert bristow-johnson in his answer: differentiators destroy this information (such as taking a derivative in continuous time destroys evidence of any constant value in the original function).

To sum up, I believe that the proof is flawed because the procedure followed could use any function of the form $u[n]+C$ with $C\in\mathbb{R}$, and this would lead to many functions having the same Fourier transform, which is indeed wrong as the Fourier transform is a bijection. Maybe the author deliberately decided to ignore anything related to DC values, conscious that in order to show that $F(\omega)$ is the DTFT of $f[n]$ he would need the accumulation property (whose most popular proof is derived from the DTFT of the unit step - ergo, a pretty circular proof). The proof is not strictly wrong, as everything it states (the formulae for $F(\omega)$ and $U(\omega)$, the decomposition of the unit step, the difference equation) is true, but it would require the accumulation property to show why $F(\omega)$ doesn't have any Dirac deltas.

Answer 2

I was overwhelmed by the number of responses I got (10 answers so far!). Of course, all of them got my upvote. This was fun, thanks guys for your thoughts, comments, etc. I know that by now most of you know what the flaw is, at least the one I meant. People express things differently, and there's always room for misunderstandings, so I will try to clearly formulate what I think is the most important flaw in that derivation. I'm aware of the fact that not everybody will agree and that's fine. I'm happy to be able to discuss this sort of esoteric DSP topics with such sharp minds as y'all are! Here we go.

My first claim is that each and every equation in my question is correct. However, the derivation and motivation of some of them is totally wrong and misleading, and that "derivation" can only exist because the author knew what the result was supposed to look like.

Eq. (3) in the question ($f[n]-f[n-1]=\delta[n]$) is correct for the given sequence $f[n]$ (Eq. $(2)$ in the question), but it is clearly also correct for all sequences of the form $$f[n]=u[n]+c\tag{1}$$ with some arbitrary constant $c$. So, according to the derivation, the resulting DTFT $F(\omega)$ should be the DTFT of all sequences of the form $(1)$, regardless of the value of the constant $c$. That's of course non-sense because the DTFT is unique. Specifically, using that very "proof" I could "show" that $F(\omega)$ as given in Eq. $(5)$ of my question (or Eq. $(3)$ below) is actually the DTFT of $u[n]$ that we're looking for. So why bother splitting up $u[n]$ as in Eq. $(1)$ of the question?

However, it is true that the DTFTs of all sequences $(1)$ do satisfy Eq. $(4)$ in the question (repeated here for convenience): $$F(\omega)\left(1-e^{-j\omega}\right)=1\tag{2}$$ But now comes the actual mathematical flaw: From Eq. $(2)$ it is incorrect to conclude $$F(\omega)=\frac{1}{1-e^{-j\omega}}\tag{3}$$ Eq. $(3)$ is only one of infinitely many possible solutions of $(2)$, and it conveniently happens to be the one needed by the author to arrive at the correct end result. Eq. $(3)$ is the DTFT of $f[n]$ in $(1)$ with $c=-\frac12$, but from the given derivation there is no way to know that.

So how can we avoid that mathematical error and use $(2)$ to derive the DTFTs of $all$ sequences $(1)$, with any constant $c$? The correct conclusion from $(2)$ is $$F(\omega)=\frac{1}{1-e^{-j\omega}}+\alpha\delta(\omega)\tag{4}$$ with some yet undetermined constant $\alpha$. Plugging $(4)$ into the left-hand side of $(2)$ gives $$1+\alpha (1-e^{-j\omega})\delta(\omega)=1+\alpha (1-e^{-j\omega})\Big{|}_{\omega=0}\cdot\delta(\omega)=1+0\cdot\delta(\omega)=1$$ So all functions $F(\omega)$ given by $(4)$ satisfy $(2)$, as required.

The constant $\alpha$ in $(4)$ can be determined from the value of $f[n]$ at $n=0$: $$f[0]=1+c=\frac{1}{2\pi}\int_{-\pi}^{\pi}F(\omega)d\omega=\frac{1}{2\pi}\int_{-\pi}^{\pi}\frac{d\omega}{1-e^{-j\omega}}+\frac{\alpha}{2\pi}\tag{6}$$ It can be shown, and also WolframAlpha agrees, that the Cauchy principal value of the integral in $(6)$ is $$PV\int_{-\pi}^{\pi}\frac{d\omega}{1-e^{-j\omega}}=\pi\tag{7}$$ From $(6)$ and $(7)$ we get $$\alpha=\pi (1+2c)\tag{8}$$ So for $c=-\frac12$ we get $\alpha=0$ (which corresponds to the original sequence $f[n]$ as used by the author of the proof), and for $c=0$ (i.e., for $f[n]=u[n]$) we have $\alpha=\pi$, which finally gives us the desired DTFT of $u[n]$: $$U(\omega)=\frac{1}{1-e^{-j\omega}}+\pi\delta(\omega)\tag{9}$$

Answer 3

if you allow me to divide by zero, i can prove to you that $1=2$. when you say $$F(\omega)\left(1-e^{-j\omega}\right)=1$$ there is a problem about multiplying something by zero (when $\omega=2k\pi \text{ for } k \in \mathbb{Z}$) and expecting the product to equal one.

Answer 4

The Equation (4) should be written as $$\lim_{N \to \infty} \sum_{n=-N}^{n=N}f[n]e^{-j\omega n} (1-e^{-j\omega n})+(e^{j\omega N}f[N]+e^{-j\omega N}f[-N])e^{-j\omega}=1$$ For $f[n]=u[n]$, $$\lim_{N \to \infty} \sum_{n=-N}^{n=N}f[n]e^{-j\omega n} (1-e^{-j\omega n})+e^{j\omega N}e^{-j\omega}=1$$ that is not (5). I don't know how to fix the proof without avoiding (3).

Answer 5

I think I have figured out the best way to express the flaw in this proof. So I am going to give it another stab.

The choice of $\frac{1}{2}$ in (1) is arbitrary. Let's replace it with $x$. Follow the proof through, and end up with:

$$ U(\omega)=\frac{1}{1-e^{-j\omega}}+2\pi x \delta(\omega) $$

There is nothing in the proof which constrains $x$ to be $\frac{1}{2}$, it can take any finite value and the proof works the same.

Furthermore, if you take the step I did in my last answer and find (4) is expressed as

$$ F( \omega )(1 - e^{-j\omega} ) = 1 + 2\pi x (1 - e^{-j\omega} ) \delta(\omega) $$

Followed by including it in (5) and (6) you get:

$$ U(\omega)=\frac{1}{1-e^{-j\omega}}+ 4\pi x \delta(\omega) $$

Which, as I pointed out earlier, is inconsistent with the definition to get there.

This proof fails to show that $ x = \frac{1}{2}$, and it seems to indicate that for any defined x, inconsistent results will follow. Therefore I go back to the statement in my first answer that the value of $ \pi $ for the coefficient of $ \delta(\omega) $ is a definitional act, not an mathematical truism.

Perhaps there is some other situation which makes $x=\frac{1}{2}$ the correct value, but this proof doesn't provide it.

Ced

Answer 6

The flaw follows the word "Obviously", if that is supposed to be the Dirac Delta Function.

Here is the draft of an answer for your other question that I never posted:

---------------------------------------------------------------

I don't think a proof is possible. This may be a case of a "functional definition" having desired properties.

$$ X_{2\pi} \left(\omega\right) = \sum\limits_{n=-\infty}^{+\infty} x[n] e^{-j \omega n} $$ $$ U = \sum\limits_{n=0}^{+\infty} e^{-j \omega n} $$ $$ U = \lim_{ N \to \infty } \sum\limits_{n=0}^{N-1} e^{-j \omega n} $$ $$ U = \lim_{ N \to \infty } \left[ \frac{ 1 - e^{-j \omega N} }{ 1 - e^{-j \omega } } \right] $$ $$ U = \frac{ 1 }{ 1 - e^{-j \omega } } - \lim_{ N \to \infty } \left[ \frac{ e^{-j \omega N} }{ 1 - e^{-j \omega } } \right] $$ Looking at the last limit value. For $ \omega = 0 $ it is clear that it acts like a Dirac Delta. Why the coefficient should be $ \pi $, I don't know. It may have to do with the area of the unit circle. When $ \omega \neq 0 $, the denominator can be factored out of the limit and the numerator just jumps along the unit circle and never reaches a limit. Setting it to zero is a definitional act.

Proving the definition works in a desirable way is a different matter.

The page 138 proof is wrong (at least) because:

$$ \delta(t) = \lim_{ a \to 0 } \frac{1}{2a} \left[ u(t + a) - u(t - a) \right] = \frac{du}{dt}$$ Which is not similar in any way to $ \delta(n) = u_2(n) - u_2(n-1) $ as they define it.

Interesting situation, I hope this helps. I am looking forward to what you have to say.

Ced

Answer 7

This is in response to the comments in my first answer. Because of the spoiler cloaking I am posting it as a separate answer.

I was going to post my other answer to the other question, but I didn't due to my lack of experience in this area. I posted it yesterday, deleted it, then undeleted, then figured out how to employ spoiler tags.

Clearly the $\delta$ function defined in the problem is not the Dirac Delta function. I looked up DTFT in Wikipedia and the DTFT for the Dirac Delta function is one. I will call the $\delta$ of the problem $\delta_p$.

$$ \delta_p[n] = f[n] - f[n-1] = u[n] - u[n-1] $$

Taking the DTFT of the left and right parts. I'm not sure I have the notations right, but the math should be clear. Using the definition that is being proved.

$$ F_p( \omega ) = F_u( \omega ) - F_u( \omega ) e^{-j\omega} $$

$$ F_p( \omega ) = \left[ \frac{1}{1-e^{-j\omega}}+\pi\delta(\omega) \right] - \left[ \frac{e^{-j\omega}}{1-e^{-j\omega}}+ ( \pi e^{-j\omega} ) \delta(\omega) \right] $$

$$ F_p( \omega ) = \frac{1-e^{-j\omega}}{1-e^{-j\omega}} + \pi (1 - e^{-j\omega} )\delta(\omega) $$

$$ F_p( \omega ) = 1 + \pi (1 - e^{-j\omega} ) \delta(\omega) \neq 1 $$

Thus the RHS of (4) is incorrect except when $\omega = 2k\pi $. [Edit: Doh, it's the Dirac Delta, so this statement is wrong. I guess it should be correct except "undefined" at $\omega = 2k\pi $. Real Analysis was my least favorite math. I am leaving this alone now.]

Ced

==============================

Followup:

It is clear that the DTFT of $\delta_p$ should be 1 when it is plugged into the definition of a DTFT. Therefore, since I got a different answer when using the definition to be proved means that the definition to be proved is not correct (in a mathematical sense). Furthermore, if you carry the correction through to the end of the proof you arrive at a different definition. Assuming the assertion to be true is used to prove that it is false.

Answer 8

To me, a first flaw appears between (3) and (4): this is an instance of the classical careless integral/infinite sum splitting. Conditions are required to allow the equation: $$ \sum (a[n] - b[n])c_\omega[n] = \sum a[n]c_\omega[n]- \sum b[n]c_\omega[n] $$ Standard $\ell_1$ or $\ell_2$ conditions might not be sharp enough. This could be related here, due to the form $f[n]-f[n-1]$, to the Fubini derivation theorem, or: When can we exchange infinite sum and discrete derivative? Ways around could revolve around monotony or Cesaro-like sums, but I shall think about this longer.

Answer 9

so Matt,

i dunno why you don't think it's problematic comparing power signals to energy signals, but suppose we modify the definition of $f[n]$ slightly:

$$ f[n] \triangleq \begin{cases} \ \tfrac12 e^{-\alpha n} \qquad & n \ge 0 \\ -\tfrac12 e^{ \alpha n} \qquad & n < 0 \\ \end{cases} $$

for some $\alpha > 0$.

now we have finite energy signals and the DTFTs should all be comparable.

$$\begin{align} f[n]-f[n-1] &= \begin{cases} \tfrac12 (e^{-\alpha n} - e^{-\alpha (n-1)}) \qquad & n > 0 \\ \tfrac12 (1 + e^{ -\alpha })\qquad & n = 0 \\ -\tfrac12 (e^{\alpha n} - e^{\alpha(n-1)})\qquad & n < 0 \\ \end{cases} \\ \\ \\ &= \begin{cases} \tfrac12 (1 - e^{\alpha}) e^{-\alpha n} \qquad & n > 0 \\ \tfrac12 (1 + e^{ -\alpha }) \qquad & n = 0 \\ \tfrac12 (e^{-\alpha} - 1)e^{\alpha n} \qquad & n < 0 \\ \end{cases} \\ \end{align}$$

i wonder what the DTFTs are? and then what happens when we let $\alpha \to 0$ ? i think there is still the problem of differentiators destroying information (and the corresponding destruction of information by multiplying by 0 in the frequency domain) that is a problem. but maybe we can lose the problem of comparing signal classes that don't share the same Hilbert space.

but, alas, it's nearly 2 a.m. and i ain't gonna deal with it now.