# Discrete-time Fourier Transform of the unit step sequence $u[n]$

From text books we know that the DTFT of $u[n]$ is given by

$$U(\omega)=\pi\delta(\omega)+\frac{1}{1-e^{-j\omega}},\qquad -\pi\le\omega <\pi\tag{1}$$

However, I haven't seen a DSP textbook that at least pretends to give a more or less sound derivation of $(1)$.

Proakis [1] derives the right half of the right-hand side of $(1)$ by setting $z=e^{j\omega}$ in the $\mathcal{Z}$-transform of $u[n]$, and says that it is valid except for $\omega=2\pi k$ (which is of course correct). He then states that at the pole of the $\mathcal{Z}$-transform we have to add a delta impulse with an area of $\pi$, but that appears more like a recipe to me than anything else.

Oppenheim and Schafer [2] mention in this context

Although it is not completely straightforward to show, this sequence can be represented by the following Fourier transform:

which is followed by a formula equivalent to $(1)$. Unfortunately, they didn't take the trouble to show us that "not completely straightforward" proof.

A book that I actually didn't know, but which I found when looking for a proof of $(1)$ is Introduction to Digital Signal Processing and Filter Design by B.A. Shenoi. On page 138 there's a "derivation" of $(1)$, but unfortunately it is wrong. I asked a "DSP-puzzle" question to have people show what is wrong with that proof.]

So my question is:

Can anybody provide a proof/derivation of $(1)$ that is sound or even rigorous while being accessible for mathematically inclined engineers? It doesn't matter if it's just copied from a book. I think it would be good to have it on this site anyway.

Note that even on math.SE almost nothing relevant is to be found: this question has no answers, and that one has two answers, one of which is wrong (identical to Shenoi's argument), and the other one uses the "accumulation property", which I would be happy with, but then one needs to proof that property, which puts you back to the start (because both proofs basically prove the same thing).

As a final note, I did come up with something like a proof (well, I'm an engineer), and I will also post it as an answer some days from now, but I would be happy to collect other published or unpublished proofs that are simple and elegant, and, most importantly, that are accessible for DSP engineers.

PS: I do not doubt the validity of $(1)$, I would just like to see one or several relatively straightforward proofs.

[1] Proakis, J.G. and D.G. Manolakis, Digital Signal Processing: Principles, Algorithms, and Applications, 3rd edition, Section 4.2.8

[2] Oppenheim, A.V. and R.W. Schafer, Discrete-Time Signal Processing, 2nd edition, p. 54.

Inspired by a comment by Marcus Müller, I'd like to show that $U(\omega)$ as given by Eq. $(1)$ satisfies the requirement

$$u[n]=u^2[n]\rightarrow U(\omega)=\frac{1}{2\pi}(U\star U)(\omega)$$

If $U(\omega)$ is the DTFT of $u[n]$, then

$$V(\omega)=\frac{1}{1-e^{-j\omega}}$$

must be the DTFT of

$$v[n]=\frac12\text{sign}[n]$$

(where we define $\text{sign}[0]=1$), because

$$V(\omega)=U(\omega)-\pi\delta(\omega)\Longleftrightarrow u[n]-\frac12=\frac12\text{sign}[n]$$

So we have

$$\frac{1}{2\pi}(V\star V)(\omega)\Longleftrightarrow \left(\frac12\text{sign}[n]\right)^2=\frac14$$

from which it follows that

$$\frac{1}{2\pi}(V\star V)(\omega)=\text{DTFT}\left\{\frac14\right\}=\frac{\pi}{2}\delta(\omega)$$

With this we get

\begin{align}\frac{1}{2\pi}(U\star U)(\omega)&=\frac{1}{2\pi}\left[(\pi\delta(\omega)+V(\omega))\star (\pi\delta(\omega)+V(\omega))\right]\\&=\frac{1}{2\pi}\left[\pi^2\delta(\omega)+2\pi V(\omega)+(V\star V)(\omega)\right]\\&=\frac{\pi}{2}\delta(\omega)+V(\omega)+\frac{\pi}{2}\delta(\omega)\\&=U(\omega)\qquad\text{q.e.d.}\end{align}

• waaah. Don't break my world. Doubt in that formula introduces a realm of chaos. For example, $u^2(t) = u(t)$, and hence (with a cont. FT definition prefactor depending constant $c$), \begin{align}\text{DTFT}(u^2)(\omega) &=c\,\cdot\, U(\omega)*U(\omega) \\&=c\pi U(\omega)+ \frac{c}{1+e^{-j\omega}}*U(\omega)\\&=c\pi \left(\pi\delta(\omega)+\frac{1}{1-e^{-j\omega}}\right)+\frac{c\pi}{1+e^{-j\omega}}+c\frac{1}{1+e^{-j\omega}}*\frac{1}{1+e^{-j\omega}}\\&=c\pi^2\delta(\omega)+\frac{2c\pi}{1+e^{-j\omega}} + c\frac{1}{1+e^{-j\omega}}*\frac{1}{1+e^{-j\omega}}\\&\overset{\text{magic?}}=U\end{align} – Marcus Müller Jan 16 '18 at 13:29
• @MarcusMüller: No doubt about that formula, it's correct. The question is just how to show it in a way that a simple minded engineer can understand. And $u^2[n]=u[n]$ works out for the given DTFT, no problem. – Matt L. Jan 16 '18 at 13:33
• I consider myself very simple-minded, and that means I worry when things don't feel "safe" when I can't see how they are derived. – Marcus Müller Jan 16 '18 at 13:47
• I see that what you're after is not to prove whether the equation is correct or not, but rather it's to rigorously and directly derive $U(w)$ from first principles and definition of DTFT. Then whenever one wants to make a rigorous proof involving impulses then I guess one should better refer to the cited books from generalized function theory: Lighthill-1958 is cited in Opp&Schafer for a discussion of impulse function and its use in Fourier transforms. All other proofs will inevitably rely on the proofs made on those references and will be insufficient to replace a rigorous proof. – Fat32 Jan 16 '18 at 16:07
• @Fat32: That's a valid viewpoint. I think, however, that a reasonably sound derivation is possible if we accept basic transforms such as $\text{DTFT}\{1\}=2\pi\delta(\omega)$, and if we're content to define integrals by their Cauchy principal value. – Matt L. Jan 16 '18 at 17:05

Cedron Dawg posted an interesting initial point in this answer. It begins with these steps:

\begin{align} U(\omega) &= \sum\limits_{n=0}^{+\infty} e^{-j \omega n} \\ &= \lim_{ N \to \infty } \sum\limits_{n=0}^{N-1} e^{-j \omega n}\\ &= \lim_{ N \to \infty } \left[ \frac{ 1 - e^{-j \omega N} }{ 1 - e^{-j \omega } } \right] \\ &= \frac{ 1 }{ 1 - e^{-j \omega } } - \lim_{ N \to \infty } \left[ \frac{ e^{-j \omega N} }{ 1 - e^{-j \omega } } \right] \end{align}

It turns out the term inside the limit can be expanded as follows:

\begin{aligned} \frac{ e^{-j \omega N} }{ 1 - e^{-j \omega } } ={} &\frac{1}{\sin^2(\omega)+(1-\cos(\omega))^2} \cdot \\ &\left[-\cos(\omega)\cos(N\omega)+\cos(N\omega)-\sin(\omega)\sin(N\omega)+ \\ j(-\sin(\omega)\cos(N\omega)+\cos(\omega)\sin(\omega)-\sin(N\omega))\right] \end{aligned}

The common factor outside the brackets can be expressed as:

$$\frac{1}{\sin^2(\omega)+(1-\cos(\omega))^2} = \frac{1}{4\sin^2(\omega/2)}$$

The real part inside the brackets also equals:

$$-\cos(\omega)\cos(N\omega)+\cos(N\omega)-\sin(\omega)\sin(N\omega)= 2\sin(\omega/2)\sin[\omega(-N+1/2)]$$

On the other hand, the imaginary part can be rewritten as:

$$-\sin(\omega)\cos(N\omega)+\cos(\omega)\sin(\omega)-\sin(N\omega)=-2\sin(\omega/2)\cos[\omega(-N+1/2)]$$

Rewritting the original term we get that:

\begin{align} \frac{ e^{-j \omega N} }{ 1 - e^{-j \omega } } &=\frac{2\sin\left(\frac \omega 2\right)}{4\sin^2\left(\frac \omega 2\right) } \left( \sin[\omega(-N+1/2)] - j\cos[\omega(-N+1/2)]\right) \\ &=-\frac{\sin[\omega(M+1/2)]}{2\sin\left(\frac \omega 2\right)} - j\frac{\cos[\omega(M+1/2)]}{2\sin\left(\frac \omega 2\right)} \end{align}

where I used $M=N-1$ and the limit stays unaffected as $M\to \infty$ as well.

According to the 7th definition in this site:

$$\lim_{M\to \infty} -\frac{1}{2\sin(\omega/2)}\sin[\omega(M+1/2)] = -\pi \delta(\omega)$$

So far we have that:

$$\lim_{ M \to \infty } \frac{ e^{-j \omega (M+1)} }{ 1 - e^{-j \omega } } =-\pi\delta(\omega) -j\lim_{M\to \infty} \frac{\cos[\omega(M+1/2)]}{2\sin(\omega/2)}$$

If we could prove that the second term on the right of the equality is $0$ in some sense, then we are done. I asked it at math.SE and, indeed, that sequence of functions tends to the zero distribution. So, we have that:

\begin{align} U(\omega) &= \frac{ 1 }{ 1 - e^{-j \omega } } - \lim_{ N \to \infty } \left[ \frac{ e^{-j \omega N} }{ 1 - e^{-j \omega } } \right] \\ &=\frac{ 1 }{ 1 - e^{-j \omega } }+\pi\delta(\omega) +j\lim_{M\to \infty} \frac{\cos[\omega(M+1/2)]}{2\sin(\omega/2)} \\ & =\frac{ 1 }{ 1 - e^{-j \omega } }+\pi\delta(\omega) \end{align}

• This is very nice! I checked it and everything seems to be correct, so that imaginary part must tend to zero in some sense. I'll think about it for a bit. – Matt L. Jan 19 '18 at 10:37
• @MattL. Let me know if you are able to make any progress! – Tendero Jan 19 '18 at 17:11
• @MattL. The proof is finally complete! – Tendero Jan 23 '18 at 2:43
• Good work! I had figured out that the cosine term would tend to zero due to the Riemann-Lebesgue lemma, but my problem was the case $\omega=0$. Because the very first formula is based on the geometric sum, which is only valid for $\omega\neq 0$. It all somehow works out after all, but that's still a minor flaw. I have another derivation that does not split out the term $1/(1-e^{-j\omega})$, in which the case $\omega=0$ is handled with a bit more care, but it's still an "engineer's proof". I might post it when I have more time. – Matt L. Jan 23 '18 at 8:11

I'll provide two relatively simple proofs that do not require any knowledge of distribution theory. For a proof that computes the DTFT by a limit process using results from distribution theory, see this answer by Tendero.

I will only mention (and not elaborate on) the first proof here, because I've posted it as an answer to this question, the purpose of which was to show that a certain published proof is faulty.

The other proof goes as follows. Let's first write down the even part of the unit step sequence $u[n]$:

$$u_e[n]=\frac12\left(u[n]+u[-n]\right)=\frac12+\frac12\delta[n]\tag{1}$$

The DTFT of $(1)$ is

$$\text{DTFT}\{u_e[n]\}=\pi\delta(\omega)+\frac12\tag{2}$$

which equals the real part of the DTFT of $u[n]$:

$$U_R(\omega)=\text{Re}\{U(\omega)\}=\pi\delta(\omega)+\frac12\tag{3}$$

Since $u[n]$ is a real-valued sequence we're done because the real and imaginary parts of $U(\omega)$ are related via the Hilbert transform, and, consequently, $U_R(\omega)$ uniquely determines $U(\omega)$. However, in most DSP texts, these Hilbert transform relations are derived from the equation $h[n]=h[n]u[n]$ (which is valid for any causal sequence $h[n]$), from which it follows that $H(\omega)=\frac{1}{2\pi}(H\star U)(\omega)$. So in order to show the Hilbert transform relation between the real and imaginary parts of the DTFT we need the DTFT of $u[n]$, which we actually want to derive here. So the proof becomes circular. That's why we'll choose a different way to derive the imaginary part of $U(\omega)$.

For deriving $U_I(\omega)=\text{Im}\{U(\omega)\}$ we write the odd part of $u[n]$ as follows:

$$u_o[n]=\frac12\left(u[n]-u[-n]\right)=u[n-1]-\frac12+\frac12\delta[n]\tag{4}$$

Taking the DTFT of $(4)$ gives

\begin{align}jU_I(\omega)&=e^{-j\omega}U(\omega)-\pi\delta(\omega)+\frac12\\&=e^{-j\omega}(U_R(\omega)+jU_I(\omega))-\pi\delta(\omega)+\frac12\\&=e^{-j\omega}\left(\pi\delta(\omega)+\frac12\right)+e^{-j\omega}jU_I(\omega)-\pi\delta(\omega)+\frac12\\&=\frac12(1+e^{-j\omega})+e^{-j\omega}jU_I(\omega)\tag{5}\end{align}

where I've used $(3)$. Eq. $(5)$ can be written as

$$jU_I(\omega)(1-e^{-j\omega})=\frac12(1+e^{-j\omega})\tag{6}$$

The correct conclusion from $(6)$ is (see this answer for more details)

$$jU_I(\omega)=\frac12\frac{1+e^{-j\omega}}{1-e^{-j\omega}}+c\delta(\omega)\tag{7}$$

But since we know that $U_I(\omega)$ must be an odd function of $\omega$ (because $u[n]$ is real-valued), we can immediately conclude that $c=0$. Hence, from $(3)$ and $(7)$ we finally get

\begin{align}U(\omega)&=U_R(\omega)+jU_I(\omega)\\&=\pi\delta(\omega)+\frac12+\frac12\frac{1+e^{-j\omega}}{1-e^{-j\omega}}\\&=\pi\delta(\omega)+\frac12\left( 1+\frac{1+e^{-j\omega}}{1-e^{-j\omega}}\right)\\&=\pi\delta(\omega)+\frac{1}{1-e^{-j\omega}}\tag{8}\end{align}