Proof of Euler's Identity
This chapter outlines the proof of Euler's Identity, which is an
important tool for working with
complex numbers. It is one of the
critical elements of the
DFT definition that we need to understand.

Euler's identity (or ``theorem'' or ``formula'') is

(Euler's Identity)
To ``prove'' this, we will first define what we mean by
``

''. (The right-hand side,

, is assumed to be understood.) Since

is just a
particular
real number, we only really have to explain what we mean by
imaginary exponents. (We'll also see where

comes from in the
process.) Imaginary exponents will be obtained as a generalization of
real exponents. Therefore, our first task is to define exactly what
we mean by

, where

is any real number, and

is any
positive real number.
The ``original'' definition of exponents which ``actually makes
sense'' applies only to positive integer exponents:
where

is real.
Generalizing this definition involves first noting its abstract
mathematical properties, and then making sure these properties are
preserved in the generalization.
Properties of Exponents
From the basic definition of positive integer exponents, we have
- (1)
-
- (2)
-
Note that property (1) implies property (2). We list them both explicitly
for convenience below.
How should we define

in a manner consistent with the
properties of integer exponents? Multiplying it by

gives
by property (1) of exponents. Solving

for

then
gives
What should

be? Multiplying it by

gives, using property (1),
Dividing through by

then gives
Similarly, we obtain
for all integer values of

,
i.e.,

.
Rational Exponents
A
rational
number is a
real number that can be expressed as
a ratio of two finite
integers:
Applying property (2) of exponents, we have
Thus, the only thing new is

. Since
we see that

is the

th root of

.
This is sometimes written
The

th root of a real (or complex) number is not unique. As we all
know, square roots give two values (
e.g.,

). In the
general case of

th roots, there are

distinct values, in
general. After proving
Euler's identity, it will be easy to find them
all (see §
3.11). As an example,
![$ \sqrt[4]{1}=1$](http://www.dsprelated.com/josimages_new/mdft/img252.png)
,

,

,
and

, since

.
The closest we can actually get to most
real numbers is to compute a
rational number that is as close as we need. It can be shown that
rational numbers are
dense in the real numbers; that is,
between every two real numbers there is a rational number, and between
every two rational numbers is a real number.
3.1An
irrational number can be defined as any real
number having a non-repeating
decimal expansion. For example,

is an irrational real number whose
decimal expansion starts
out as
3.2
Every truncated, rounded, or repeating expansion is a
rational number. That is, it can be rewritten as an integer
divided by another integer. For example,
and, using

to denote the repeating part of a
decimal expansion, a repeating example is as follows:
Other examples of
irrational numbers include
Their decimal expansions do not repeat.
Let

denote the

-digit decimal expansion of an arbitrary real
number

. Then

is a rational number (some integer over

).
We can say
That is, the
limit of

as

goes to infinity is

.
Since

is defined for all

, we naturally define

as the following mathematical limit:
We have now defined what we mean by
real exponents.
A First Look at Taylor Series
Most ``smooth'' functions

can be expanded in the form of a
Taylor series expansion:
This can be written more compactly as
where `

' is pronounced ``

factorial''.
An informal derivation of this formula for

is given in
Appendix
E. Clearly, since many
derivatives are involved, a Taylor series expansion is only possible
when the function is so smooth that it can be differentiated again and
again. Fortunately for us, all audio
signals are in that category,
because
hearing is bandlimited
to below

kHz, and the audible
spectrum of any sum of
sinusoids is infinitely differentiable. (Recall
that

and

,
etc.). See §
E.6 for more about this point.
Imaginary Exponents
We may define
imaginary exponents the same way that all
sufficiently smooth real-valued functions of a real variable are
generalized to the complex case--using
Taylor series. A
Taylor series expansion is just a polynomial (possibly of infinitely
high order), and polynomials involve only addition, multiplication,
and division. Since these elementary operations are also defined for
complex numbers, any smooth function of a real variable

may be
generalized to a function of a
complex variable 
by simply
substituting the complex variable

for the real variable

in the Taylor
series expansion of

.
Let

, where

is any positive
real number and

is
real. The Taylor
series expansion about

(``
Maclaurin series''),
generalized to the complex case is then
 |
(3.1) |
This is well defined, provided the series
converges for every
finite

(see Problem
8). We have

, so the first term is no problem. But what is

? In
other words, what is the derivative of

at

? Once we find
the successive derivatives of

at

, we will have
the definition of

for any complex

.
Let's apply the definition of differentiation and see what happens:
Since the limit of

as

is less than
1 for

and greater than

for

(as one can show via direct
calculations), and since

is a continuous
function of

for

, it follows that there exists a
positive
real number we'll call

such that for

we get
For

, we thus have

.
So far we have proved that the derivative of

is

.
What about

for other values of

? The trick is to write it as
and use the
chain rule,
3.3 where

denotes
the log-base-

of

.
3.4 Formally, the chain rule tells us how to
differentiate a function of a function as follows:
Evaluated at a particular point

, we obtain
In this case,

so that

,
and

which is its own derivative. The end result is then

,
i.e.,
Above, we defined

as the particular
real number satisfying
which gave us

when

. From this expression,
we have, as

,
or
This is one way to define

. Another way to arrive at the same
definition is to ask what logarithmic base

gives that the derivative of

is

. We denote

by

.
Numerically,

is a
transcendental number (a type of
irrational
number3.5), so its
decimal expansion never repeats.
The initial
decimal expansion of

is given by
3.6
Any number of digits can be computed from the formula

by making

sufficiently small.
e^(j theta)
We've now defined

for any positive
real number 
and any
complex number 
. Setting

and

gives us the
special case we need for
Euler's identity. Since

is its own
derivative, the
Taylor series expansion for

is one of
the simplest imaginable infinite series:
The simplicity comes about because

for all

and because
we chose to expand about the point

. We of course define
Note that all even order terms are real while all odd order terms are
imaginary. Separating out the real and imaginary parts gives
Comparing the Maclaurin expansion for

with that of

and

proves Euler's identity. Recall
from introductory
calculus that
so that
Plugging into the general
Maclaurin series gives
Separating the Maclaurin expansion for

into its even and odd
terms (real and imaginary parts) gives
thus proving Euler's identity.
Back to Mth Roots
As mentioned in §
3.4, there are

different numbers

which satisfy

when

is a positive integer.
That is, the

th root of

, which is
written as

, is not unique--there are

of them. How do
we find them all? The answer is to consider
complex numbers in
polar form.
By
Euler's Identity, which we just proved, any number,
real or complex, can be written in polar form as
where

and

are
real numbers.
Since, by Euler's identity,

for every integer

, we also have
Taking the

th root gives
There are

different results obtainable using different values of

,
e.g.,

. When

, we get the same thing as
when

. When

, we get the same thing as when

, and so
on, so there are only

distinct cases. Thus, we may define the

th

th-root of

as
These are the

th-roots of the
complex number

.
Roots of Unity
Since

for every integer

,
we
can write
These are the
th roots of unity. The special case

is
called a
primitive
th root of unity,
since integer powers
of it give all of the others:
The

th roots of unity are so frequently used that they are often
given a special notation in the
signal processing literature:
where

denotes a primitive

th root of
unity.
3.7 We may also call

a
generator of the
mathematical
group consisting of the

th roots of unity and
their products.
We will learn later that the

th roots of unity are used to generate
all the
sinusoids used by the length-
DFT and its inverse.
The

th
complex sinusoid used in a DFT of length

is given by
where

,

, and

is the
sampling interval in seconds.
In §
2.10, De Moivre's theorem was introduced as a consequence of
Euler's identity:
To provide some further insight into the ``mechanics'' of Euler's
identity, we'll provide here a direct proof of De Moivre's theorem for
integer 
using
mathematical induction and elementary trigonometric
identities.
Proof:
To establish the ``basis'' of our mathematical
induction proof, we may
simply observe that De Moivre's theorem is trivially true for

. Now assume that De Moivre's theorem is true for some positive
integer

. Then we must show that this implies it is also true for

,
i.e.,
![$\displaystyle \left[\cos(\theta) + j \sin(\theta)\right] ^{n+1} = \cos[(n+1)\theta] + j \sin[(n+1)\theta]. \protect$](http://www.dsprelated.com/josimages_new/mdft/img351.png) |
(3.2) |
Since it is true by hypothesis that
multiplying both sides by
![$ [\cos(\theta) + j \sin(\theta)]$](http://www.dsprelated.com/josimages_new/mdft/img353.png)
yields
From
trigonometry, we have the following
sum-of-angle identities:
These identities can be proved using only arguments from classical
geometry.
3.8Applying these to the right-hand side of Eq.

(
3.3), with

and

, gives Eq.

(
3.2), and
so the induction step is proved.

De Moivre's theorem establishes that integer powers of
![$ [\cos(\theta) + j \sin(\theta)]$](http://www.dsprelated.com/josimages_new/mdft/img353.png)
lie on a circle of radius 1 (since

, for all
![$ \phi\in[-\pi,\pi]$](http://www.dsprelated.com/josimages_new/mdft/img364.png)
). It
therefore can be used to determine all

of the

th
roots of unity
(see §
3.12 above).
However, no definition of

emerges readily from De Moivre's
theorem, nor does it establish a definition for
imaginary exponents
(which we defined using
Taylor series expansion in §
3.7 above).
See
http://ccrma.stanford.edu/~jos/mdftp/Euler_Identity_Problems.html
Next Section: Sinusoids and ExponentialsPrevious Section: Complex Numbers