Tip:
Highlight text to annotate it
X
Welcome to Calculus. I'm Professor Greist.
We're about to begin Lecture 45 on Sequences.
We now begin the last chapter of our course, where we build a discrete
calculus, reinventing everything that we've done so
far for functions, with a digital input.
These functions or sequences will be familiar
objects to you from throughout the course,
but we'll look at them from a new perspective of discrete calculus.
Everything that we have done thus far in this course
has been for functions that might be described as analog.
They are functions whose inputs and outputs, with few exceptions, very
continuously, if not, smoothly. This allows us to talk about
limits, differentials, and build up calculus.
In contrast, so much of what we see and build is digital
and not analog built of discrete or quantized
bits, whether it's music, imagery, or information.
Many things are not amenable to smooth calculus.
For this reason, we're going to reconsider the notion of a sequence.
And we've seen sequences before, but here's a slightly different perspective.
A sequence is a discrete or digital input function with an analog
output, that is the inputs are natural numbers, the outputs are reals.
Now,
sequences are everywhere from economic data to digital
signals, but thinking of them as a function with an
input, say n, and an output, a sub n,
is going to be the focus of this chapter. The notation that
we'll use sometimes is writing out the terms of
the sequence, that is the outputs, a sub 0, a sub 1,
a sub 2, etc. Now our goal is going to
be to redo everything that we have done in this Calculus class,
but in a digital form or a discrete form,
for functions with a discrete input. That is, for
sequences.
All of the many things that we have discovered,
so far, have digital images in this discrete Calculus.
We'll begin as we began this course
with examples of interesting functions or sequences.
For example, there are many sequences that are polynomial, like n squared.
Other sequences do not grow like a polynomial, but are rather
exponential, like the sequence 2 to the n. How would
you describe the sequence 1, negative 1, 1 negative 1 repeating.
Well, seems a little odd at first but one could describe
this as a trigonometric function. For example, as cosine
with n times high. Now, more interesting sequences
are out there. For example, what if we remove the pi and
consider the sequence cosine n. If we plot the
terms of that sequence as a function of n, we see a curious mixture
of wavelike behavior, but non-repeatability.
The sequence never repeats. And in that
way, it's a little bit unlike the trigonometric
function cosine. This phenomenon is rather curious.
You've seen it before, if you've ever seen an object that spins so fast that your
visual refresh rate can't keep up with it. And it looks like it's spinning
at a different rate or even in a different direction.
This is sometimes called aliasing.
Let's begin our construction of discrete calculus with the notion of a limit.
Now, what does it mean to take the limit of a sequence?
Well, I believe our adventure begins with failure.
Because of the discrete input,
it doesn't make sense to talk about getting as close as you want
2n equals eleven. The one circumstance, under which it does
make sense, is to take a limit as n goes to infinity in this setting.
Then, the original definition of the limit, as n goes to infinity, makes sense.
We say that
that limit is L if for every epsilon we find
some value, say, capital M, past which the
output of the function lies within epsilon of the limit.
This has to continue for any value of epsilon that is desired.
As we change the tolerance on the output,
we can find a new tolerance on the input in order to
satisfy the condition. So with that in mind, why?
Why would we bother taking limits of sequences?
Well, you've done so already in
the context of Taylor series and approximation.
We began this very course with a discussion of what
E was in terms of the limit of
a sequence. E is 1 plus 1 plus one half
plus one sixth, and each of these finite sums
can be thought of as a term in a sequence whose limit is e.
At other times in this course we've implicitly assumed that we
can take a limit of a sequence. We did so in Newton's Method,
where we glibly stated that we hope the limit
of this sequence of points converges to the root that we were looking for.
Now, all of this is good motivation but how does one compute limits.
The principle that we'll
see over and over again is that one can use continuous methods
to solve discrete problems. Let's see a simple example.
Consider the sequence, a sub n equals 1 plus alpha over n to the nth power.
You've seen this before, in the context where n is x, a continuous variable.
Solving for the limit as n goes
to infinity, follows the
exact same method. We take the log of both sides, pull that
log inside the limit, and use it to remove the exponent n
out in front. Then, we use our knowledge of
Taylor series to expand that logarithm, as alpha
over n plus big O of 1 over n squared.
And this is the key point that our use of Taylor Theories and
big O works just as well in the discrete setting, as in the continuous.
And so we can evaluate the limit, exponentiate
and get an answer that should be very familiar.
Another example would
be a sub n equals 2n squared minus n
square root of quantity 4n squared
plus 5. We would attack this by doing some
algebraic manipulation, factoring out a 2n squared.
What is left is of the form 1 minus square root of 1 plus 5 over
4n squared. Here we see another Taylor series lurking.
That involving the square root using the binomial
series we can obtain after a little bit of algebraic
simplification that the leading ordered term is negative 5
4ths. Everything else is in big O of 1
over n squared. And so when we take the limit, we obtain
negative 5 4ths. Now not every limit is so transparent.
For example, what would do if asked to evaluate
something of the form, square root of 2 plus
square root of 2 plus square root of 2
plus square root of 2, et cetera, all nested?
Well,
the appropriate way to handle something like this is to realize it as the limit
of a sequence, where we build things up, step by step beginning with root 2.
.And then, with root 2 plus root 2, et cetera.
We want to compute the limit of this sequence A sub N.
Now in order to do so there's one difficult and
critical step that is, you need to
determine the recursion relation, that the terms satisfy.
In this case, I'll tell you that it is the following, a sub n equals square
root of 2 plus a sub n minus 1.
Let's say I give you that recursion relation.
How do you compute the limit? Let us,
as before, denote this limit, iL. And then, apply the limit to the
recursion relation. On the left, we have the limit.
goes to infinity of a sub n, that's L.
On the right, we have an a sub n minus 1 term.
What's the limit of that, as n goes to infinity?
Well, of course, it, too, must be L.
Now, we're assuming that we can slip that limit in under the square root.
Let's forget about whether that's legal or not and see what happens when we
try to simplify this algebraically. Squaring
both sides, we obtain L squared equals 2
plus L. With a little bit of rearrangement, we get
a polynomial that easily factors into L minus 2 and L plus 1.
Now, this polynomial has two solutions, namely negative 1 and
positive 2. We know that the limit of this sequence is
not a negative number. And, therefore, if the limit exists it
must be equal to 2. Indeed, the limit does
exist and is 2. Let's look at another limit
of this form. In this case, 1 plus 1 over 1 plus
1 over 1 plus 1, et cetera. All nested together.
As before, we can write out a sequence that gets closer and closer
to this. A not is one, a 1 is 1 over 1 plus 1.
A2 is 1 over 1 plus 1 over 1 over 1, or something like that, I don't know.
It keeps going.
The tricky part
in this case is to find the recurrence relation that these terms satisfy.
Once again, I'm going to tell you what it is.
It is that a sub n equals 1 plus 1 over a sub n minus 1.
This instruction tells you how to build the
next term in order to compute the limit
of the a sub n's.
We followed the same procedures before
taking the limit of the recursion relation.
Substituting an L for a sub n and a sub n minus 1.
And, then, with a little bit of algebraic rearrangement, what do we see?
We get L squared minus L minus 1 equals 0. This has
roots 1 plus or minus square root of 5 over 2.
One of these is negative, the other positive.
We'll take that positive square root, and that is our limit.
This particular value is of some independent interest.
It is sometimes called the golden ratio and given the symbol phi,
equals 1 plus root 5 over 2. Oh,
perhaps you've see the Golden Ratio before in the context of some other sequences.
Perhaps you've seen the Fibonacci Sequence, that begins with 0, 1, 1, 2, 3,
5, 8, 13, 21,34, 55, 89, et cetera.
There's a lot of interesting mathematics hiding behind here.
If you'd like, you might want to take a look at the bonus material
for hint of what Calculus will be able to tell us about the Fibonacci Sequence.
We began this course in Calculus, with the discussion
of functions and a contemplation of the exponential function.
In the same manner we've begun our construction of the
discrete Calculus by considering functions or sequences.
In our next lesson, we'll look at the discrete analogue, the expidential
function, and see how it
relates to derivatives.