Unizor - Derivatives - Limit of Sequence - Big O, Little o

Notes to a video lecture on http://www.unizor.com

Rate of Change: Big-O, Little-o

Consider two infinitely growing sequences
{n} and {n+1}.
Both are infinitely growing, the second one is always (for any order number n) greater than the first, so it is "bigger" in some sense.
But, if you compare the rate of their growth, it is, actually, the same. When one doubles in value, another almost doubles too and the difference gets proportionally smaller and smaller.
The difference between these sequences, as they grow, is always 1, but their values are getting larger and larger, so proportional difference is getting more and more negligible. For order number n=10 the difference of 1 represents 10% of the value, for n=1000 the difference of 1 represents only 0.1% of the value. This allows us to say that both sequence are growing at the same rate.

On the other hand, if you consider these infinitely growing sequences
{n} and {ln(n)},
you will soon see that proportional difference becomes larger and larger as n growth much faster than ln(n). For order number n=10 the first sequence has value 10, while the second, approximately, has 2.3 - 77% difference. For n=1000 the first sequence has value 1000, while the second, approximately, has 6.9 - more than 99% difference. And this proportional difference is growing. This allows us to say that the first sequence growth proportionally faster than the second. The rate of growth of the first sequence is greater than of the second.

Similar situation is with infinitesimals.
Consider two infinitesimal sequences
{1/n} and {10/n}.
Both are infinitesimal, though the first one is always smaller. Proportional difference between them is always 9/n, which represents 900% of the value of the first sequence. It does not change and, therefore, we can say that these two infinitesimals are diminishing with the same speed.

On the other hand, if you consider these infinitesimals
{1/n} and {1/ln(n)},
you will see that proportional difference is increasing as 1/n converges to zero much faster than 1/ln(n). Indeed, with order number n=10 the first sequence equals 0.1, while the second, approximately, is 0.4343 - more than 300% difference. For n=100 the first sequence is 0.01, while the second, approximately, is 0.2174 - more than 2000% difference. For n=1000 the first sequence is 0.001, while the second is 0.1448 - more than 14000% difference.

To address the relative rate of growth for infinitely growing sequences or relative rate of diminishing for infinitesimal sequences, there is a special notation called Big-O and Little-o.
Big-O means similar rate of change, while Little-o means "smaller" in terms of rate of change (slower growth for infinitely growing and faster diminishing for infinitesimals).

It should be noted that many sources differentiate between relative rates of change bounded from above (where it's called Big-O), from below (where it's called Ω) and from both sides (where it's called Θ).
For our purposes we will use only Big-O and assume that it refers to a relative rate of change bounded from both upper and lower sides. The definition below clarifies the exact meaning of this.

Thus, considering infinitely growing sequences, we can say that
n+1 = O(n) - to indicate the same rate of change or the same order of growing,
ln(n) = o(n) - to indicate that ln(n) is "smaller" in a sense of the rate of growing of ln(n) to infinity is slower than the rate of growing of n.

For infinitesimal sequences we can say that
10/n = O(1/n) - to indicate that both infinitesimals are diminishing to zero with the same speed, their order of diminishing is the same,
1/n = o(1/ln(n)) - to indicate that 1/n is "smaller" in a sense of the rate of diminishing to zero of 1/n is faster than the rate of diminishing to zero of 1/ln(n).

Let's now define Big-O and Little-o more rigorously.

Consider two sequences
{X_n} and {Y_n}.
Definition of Little-o is based on the behavior of their ratio {X_n/Y_n} (assuming Y_n≠0).
If this ratio is an infinitesimal sequence, we say that
X_n = o(Y_n)
Symbolically, the rate of change of X_n is o(Y_n) if
∀ε>0 ∃N: n ≥ N ⇒ |X_n/Y_n| ≤ ε

Definition of Big-O for two positive infinitely growing or infinitesimal sequences {X_n} and {Y_n} is also based on the ratio {X_n/Y_n}.
If, after certain order number, it is bounded from both sides by positive numbers, we say that these two sequences are of the same rate of change (or of the same order).
Symbolically, the rate of change of X_n is O(Y_n) if
∃ A > 0, B > 0, N:
n ≥ N ⇒ A ≤ X_n/Y_n ≤ B

Examples

1. Infinitely Growing - O()
X_n = 2n²+n−1; Y_n = n²−1
X_n/Y_n = (2n²+n−1)/(n²−1) =
= [(2n²−2)+(n+1)]/(n²−1) =
= 2+[(n+1)/(n²−1)] =
= 2+[1/(n−1)]
The last expression is, obviously, limited between A=2 and B=3 for n ≥ 2.
Therefore, X_n is O(Y_n).

2. Infinitesimals - O()
X_n = 1/n; Y_n = n/(n²−1)
X_n/Y_n = (n²−1)/n² =
= 1−1/n²
The last expression is, obviously, limited between A=0.5 and B=1 for n ≥ 2.
Therefore, X_n is O(Y_n).

3. Infinitely growing - o()
X_n = ln(n); Y_n = n
X_n/Y_n = ln(n)/n = ln(n^1/n)
Expression n^1/n converges to 1.
Here is a proof (with a help of a trick).
Let Z_n=n^1/n−1.
Obviously, Z_n ≥ 0.
Consider an expression
(1+Z_n)ⁿ.
On one hand, it is equal to
(1+n^1/n−1)ⁿ = n.
On the other hand, let's use Newton's binomial for it:
(1+Z_n)ⁿ = Σ_i∈[0,n]C_nⁱZ_nⁱ
Replacing the left side with n and leaving only one member of the sum on the right - the one with Z_n² - we come up with the following inequality:
n ≥ C_n²Z_n²
Since C_n² = n(n−1)/2,
n ≥ Z_n²n(n−1)/2 or
Z_n² ≤ 2/(n−1),
which proves that Z_n is an infinitesimal variable and, therefore, n^1/n→1.
Therefore, ln(n^1/n) is converging to 0.
Therefore, X_n is o(Y_n).

4. Infinitesimals - o()
X_n = 1/2ⁿ; Y_n = 1/n
X_n/Y_n = n/2ⁿ;
The expression n/2ⁿ is converging to zero.
Here is a proof.
Use Newton's binomial for identity 2ⁿ = (1+1)ⁿ:
2ⁿ = Σ_i∈[0,n]C_nⁱ
Using only one member of the sum on the right, we come up with an inequality
2ⁿ ≥ n(n−1)/2
from which follows
n/2ⁿ ≤ 2/(n−1).
Therefore, n/2ⁿ is an infinitesimal.
Therefore, X_n is o(Y_n).

.

Unizor - Derivatives - Limit of Sequence - Big O, Little o

Notes to a video lecture on http://www.unizor.com

Rate of Change: Big-O, Little-o

Consider two infinitely growing sequences
{n} and {n+1}.
Both are infinitely growing, the second one is always (for any order number n) greater than the first, so it is "bigger" in some sense.
But, if you compare the rate of their growth, it is, actually, the same. When one doubles in value, another almost doubles too and the difference gets proportionally smaller and smaller.
The difference between these sequences, as they grow, is always 1, but their values are getting larger and larger, so proportional difference is getting more and more negligible. For order number n=10 the difference of 1 represents 10% of the value, for n=1000 the difference of 1 represents only 0.1% of the value. This allows us to say that both sequence are growing at the same rate.

On the other hand, if you consider these infinitely growing sequences
{n} and {ln(n)},
you will soon see that proportional difference becomes larger and larger as n growth much faster than ln(n). For order number n=10 the first sequence has value 10, while the second, approximately, has 2.3 - 77% difference. For n=1000 the first sequence has value 1000, while the second, approximately, has 6.9 - more than 99% difference. And this proportional difference is growing. This allows us to say that the first sequence growth proportionally faster than the second. The rate of growth of the first sequence is greater than of the second.

Similar situation is with infinitesimals.
Consider two infinitesimal sequences
{1/n} and {10/n}.
Both are infinitesimal, though the first one is always smaller. Proportional difference between them is always 9/n, which represents 900% of the value of the first sequence. It does not change and, therefore, we can say that these two infinitesimals are diminishing with the same speed.

On the other hand, if you consider these infinitesimals
{1/n} and {1/ln(n)},
you will see that proportional difference is increasing as 1/n converges to zero much faster than 1/ln(n). Indeed, with order number n=10 the first sequence equals 0.1, while the second, approximately, is 0.4343 - more than 300% difference. For n=100 the first sequence is 0.01, while the second, approximately, is 0.2174 - more than 2000% difference. For n=1000 the first sequence is 0.001, while the second is 0.1448 - more than 14000% difference.

To address the relative rate of growth for infinitely growing sequences or relative rate of diminishing for infinitesimal sequences, there is a special notation called Big-O and Little-o.
Big-O means similar rate of change, while Little-o means "smaller" in terms of rate of change (slower growth for infinitely growing and faster diminishing for infinitesimals).

It should be noted that many sources differentiate between relative rates of change bounded from above (where it's called Big-O), from below (where it's called Ω) and from both sides (where it's called Θ).
For our purposes we will use only Big-O and assume that it refers to a relative rate of change bounded from both upper and lower sides. The definition below clarifies the exact meaning of this.

Thus, considering infinitely growing sequences, we can say that
n+1 = O(n) - to indicate the same rate of change or the same order of growing,
ln(n) = o(n) - to indicate that ln(n) is "smaller" in a sense of the rate of growing of ln(n) to infinity is slower than the rate of growing of n.

For infinitesimal sequences we can say that
10/n = O(1/n) - to indicate that both infinitesimals are diminishing to zero with the same speed, their order of diminishing is the same,
1/n = o(1/ln(n)) - to indicate that 1/n is "smaller" in a sense of the rate of diminishing to zero of 1/n is faster than the rate of diminishing to zero of 1/ln(n).

Let's now define Big-O and Little-o more rigorously.

Consider two sequences
{X_n} and {Y_n}.
Definition of Little-o is based on the behavior of their ratio {X_n/Y_n} (assuming Y_n≠0).
If this ratio is an infinitesimal sequence, we say that
X_n = o(Y_n)
Symbolically, the rate of change of X_n is o(Y_n) if
∀ε>0 ∃N: n ≥ N ⇒ |X_n/Y_n| ≤ ε

Definition of Big-O for two positive infinitely growing or infinitesimal sequences {X_n} and {Y_n} is also based on the ratio {X_n/Y_n}.
If, after certain order number, it is bounded from both sides by positive numbers, we say that these two sequences are of the same rate of change (or of the same order).
Symbolically, the rate of change of X_n is O(Y_n) if
∃ A > 0, B > 0, N:
n ≥ N ⇒ A ≤ X_n/Y_n ≤ B

Examples

1. Infinitely Growing - O()
X_n = 2n²+n−1; Y_n = n²−1
X_n/Y_n = (2n²+n−1)/(n²−1) =
= [(2n²−2)+(n+1)]/(n²−1) =
= 2+[(n+1)/(n²−1)] =
= 2+[1/(n−1)]
The last expression is, obviously, limited between A=2 and B=3 for n ≥ 2.
Therefore, X_n is O(Y_n).

2. Infinitesimals - O()
X_n = 1/n; Y_n = n/(n²−1)
X_n/Y_n = (n²−1)/n² =
= 1−1/n²
The last expression is, obviously, limited between A=0.5 and B=1 for n ≥ 2.
Therefore, X_n is O(Y_n).

3. Infinitely growing - o()
X_n = ln(n); Y_n = n
X_n/Y_n = ln(n)/n = ln(n^1/n)
Expression n^1/n converges to 1.
Here is a proof (with a help of a trick).
Let Z_n=n^1/n−1.
Obviously, Z_n ≥ 0.
Consider an expression
(1+Z_n)ⁿ.
On one hand, it is equal to
(1+n^1/n−1)ⁿ = n.
On the other hand, let's use Newton's binomial for it:
(1+Z_n)ⁿ = Σ_i∈[0,n]C_nⁱZ_nⁱ
Replacing the left side with n and leaving only one member of the sum on the right - the one with Z_n² - we come up with the following inequality:
n ≥ C_n²Z_n²
Since C_n² = n(n−1)/2,
n ≥ Z_n²n(n−1)/2 or
Z_n² ≤ 2/(n−1),
which proves that Z_n is an infinitesimal variable and, therefore, n^1/n→1.
Therefore, ln(n^1/n) is converging to 0.
Therefore, X_n is o(Y_n).

4. Infinitesimals - o()
X_n = 1/2ⁿ; Y_n = 1/n
X_n/Y_n = n/2ⁿ;
The expression n/2ⁿ is converging to zero.
Here is a proof.
Use Newton's binomial for identity 2ⁿ = (1+1)ⁿ:
2ⁿ = Σ_i∈[0,n]C_nⁱ
Using only one member of the sum on the right, we come up with an inequality
2ⁿ ≥ n(n−1)/2
from which follows
n/2ⁿ ≤ 2/(n−1).
Therefore, n/2ⁿ is an infinitesimal.
Therefore, X_n is o(Y_n).

.

Unizor - Derivatives - Normal to Parametric Curve

Notes to a video lecture on http://www.unizor.com

Normal to Parametric Curves

We continue dealing with a curve on the plane that is parametrically defined by two functions - its coordinates that depend on some parameter{x(t);y(t)}, where both functions x(t) and y(t) are given and differentiable.

Our task is to find an equation that describes the normal to this curve at some point {x₀;y₀} that corresponds to a parameter value t=t₀, that is x₀=x(t₀) and y₀=y(t₀).

Geometrically speaking, a normal to a curve at some point is defined as a line perpendicular to a tangential line at that same point.
Here is how it looks.



Generally, a straight line that goes through point {x₀;y₀} has a point-slope equation
y−y₀ = m·(x−x₀)
So, all we have to determine in the equation for a normal that goes through point {x₀;y₀} is its slope m.

Since a normal to a curve at some point is, by definition, perpendicular to a tangential line at the same point, we can find the slope of a tangential line first and then turn the line by 90^o.

From the previous lecture we know that the slope of a tangential line can be calculated as
m = D_t=t0[y(t)] /D_t=t0[x(t)]

If a tangential line forms angleθ with positive direction of the X-axis, and we have determined that tan θ = m (see formula form above), we can determine the angle ν formed by a normal that is perpendicular to a tangential line and positive direction of the X-axis as follows:
ν = θ−90^o

Now we determine the slope n of the normal using the following simple trigonometry:
n = tan(ν) = tan(θ−90^o) =
= −tan(90^o−θ) = −cot(θ) =
= −1/tan(θ) = −1/m =
= −D_t=t0[x(t)] /D_t=t0[y(t)]
since cot(θ)=1/tan(θ) and assuming that derivatives, participating in these calculations, are not equal to zero at point t=t₀.

The equation defining a normal will then look like this:
(y−y₀) = −D_t=t0[x(t)](x−x₀)/D_t=t0[y(t)]

Unizor - Derivatives - Parametric Curves

Notes to a video lecture on http://www.unizor.com

Differentiation
of Parametric Curves

Let's assume that we deal with some curve on the plane that is defined not as a graph of certain function that looks like y=f(x)(where x is abscissa and y - ordinate), but parametrically, where both coordinates are defined as functions of some parameter t.
An obvious example is a point moving on a plane, and its position {x;y} depends on a time parameter, so it can be described as {x(t);y(t)}, where both functions x(t) and y(t) are given and differentiable.
So, one independent parameter t describes both coordinates through these two function.

Our task is to find an equation that describes the tangential line to this curve at some point{x₀;y₀} that corresponds to a parameter value t=t₀, that is x₀=x(t₀) and y₀=y(t₀).

Geometrically speaking, a tangential line to a sufficiently smooth curve at some point is a limit of a secant line that intersects our curve at point where a tangential line should be and another point close to it, when that other point is getting closer and closer to the point of tangency.



Generally, a straight line that goes through point {x₀;y₀} has a point-slope equation
y−y₀ = m·(x−x₀)
So, all we have to determine in the equation for a tangential line that goes through point{x₀;y₀} is its slope m.

Since our tangential line is a limit of a secant, we can assume that the slope of a tangential line is the limit of a slope of a secant as the other point of secant's intersection with our curve is getting infinitesimally close to point {x₀;y₀}.

Consider a point of tangency{x₀=x(t₀);y₀=y(t₀)} and give an increment to parameter t from its value t₀ to value t₀+Δt.
The new point on a curve that corresponds to an incremented value of parameter t will be
{x₁=x(t₀+Δt);y₁=y(t₀+Δt)}

A secant that intersects our curve at points {x₀;y₀} and{x₁;y₁} has a slope equal to
m = (y₁−y₀)/(x₁−x₀)
which can be transformed into
m = Δy/Δx
where Δy=y(t₀+Δt)−y(t₀)
and Δx=x(t₀+Δt)−x(t₀)

Obviously, we want to express the limit of this expression for slope m as Δt→0 in terms of derivatives D_t[x(t)] and D_t[y(t)].
For this we can transform it into
m = (Δy/Δt)/(Δx/Δt)
from which follows that for Δt→0
m→m₀=D_t=t0[y(t)] /D_t=t0[x(t)]
where derivatives are taken at point t=t₀.

Example

A unit circle with a center at the origin of coordinates can be described parametrically with an angle θ from the positive direction of the X-axis to a radius to a point on a circle being a parameter. Let's use the radian measure of this angle.

Any point on a circle with coordinates {x;y} can be described through functions:
x=cos(θ),
y=sin(θ).

Let's choose a point that corresponds to a parameter value θ=π/4 and determine the equation of a tangential line at this point.
First of all, determine the coordinates of a point of tangency:
x=cos(π/4)=√2/2
y=sin(π/4)=√2/2
Now the slope should be equal to a ratio of derivatives of functions y(θ) and x(θ) at point with parameter θ=π/4:
D_θ=π/4[y(θ)]=D_θ=π/4[sin(θ)]=
= cos(π/4) = √2/2
D_θ=π/4[x(θ)]=D_θ=π/4[cos(θ)]=
= −sin(π/4) = −√2/2

The slope m of our tangential line is a ratio of the two values above:
m = (√2/2)/(−√2/2) = −1

So, the equation of our tangential line at point defined by parameter θ=π/4 in point-slope form is
y−√2/2 = −1·(x−√2/2)
or, in a standard form,
y = −x + √2

Unizor - Derivatives Example - arcsin(x)

Notes to a video lecture on http://www.unizor.com

Derivative Example -
Inverse Trigonometric Functions

f(x) = arcsin(x)

f ^I(x) = 1/√1−x²


Proof

We will use the method ofimplicit differentiation to obtain the formula for a derivative of this function.

Let's start from a definition of function arcsin(x).

The domain of this function is[−1,1] and its values are in[−π/2,π/2].

Then, for any value of the argument x from its domain the function value y is defined as an angle in radians such that
(a) sin(y)=x
(b) −π/2 ≤ y ≤ π/2

The first statement can be expressed as
sin(arcsin(x))=x
Since these two functions,A(x)=sin(arcsin(x)) andB(x)=x, are equal within domain [−1,1], their derivatives are equal as well.

The derivative of the A(x) can be obtained using the chain rule for compounded functions.
A^I(x)=d/dx[sin(arcsin(x))] =
cos(arcsin(x))·d/dx[arcsin(x)]

The derivative of B(x) is trivial.
B^I(x) = d/dx[x] = 1

From equality of these two derivatives we conclude
d/dx[arcsin(x)]=1/cos(arcsin(x))

Now let's analyze the expression cos(arcsin(x)).
We know that
sin(arcsin(x))=x and
arcsin(x)∈[−π/2,π/2].
Therefore,
cos(arcsin(x)) ≥ 0.
Hence,
cos(arcsin(x)) = √1−x²

The final formula for a derivative is
[arcsin(x)]^I = 1/√1−x²

A small detail remains whenx = ±1, which results in zero denominator. These are the points where our functionarcsin(x) is not differentiable.
Geometrically, it signifies that tangential lines at both ends,x=−1 and x=1, of the domain of function arcsin(x) are vertical, as can be seen from a graph of this function below:

Unizor - Derivatives - Implicit Differentiation

Notes to a video lecture on http://www.unizor.com

Implicit Differentiation

The method of implicit differentiation can be used to find a derivative of a function, implicitly defined by an equation that contains both argument and function value, for example
x² + y² = R²
where y is a function of x.

In some cases (like the one above) we can start from resolving the given equation for y as an explicit formula (like y = ±√R²−x²) and then take a derivative.
In other cases it might be impossible or impractical to resolve it for y, and these are the cases where implicit differentiation would be useful.

Consider the following problem, from which the method will be clear.

Problem 1

The function is given by the following implicit equation
x² + y² = sin(y)
that cannot be explicitly resolved for y.
Our purpose is to express the derivative dy/dx in terms of x and y.

Solution

Assuming that y is some unknown function of x, we consider the defining equation as the equality between two functions: x² + y² and sin(y).
Since these two functions are equal, their derivatives must be equal as well:
[x² + y²]^I = [sin(y)]^I

Using the property of derivative of a sum and the chain rule for compound functions, this produces:
[x²]^I + [y²]^I = [sin(y)]^I
2·x + 2·y·y^I = cos(y)·y^I
This can be resolved for y^I to get its expression in terms of x and y:
y^I = 2x/(cos(y)−2y)

Let's exemplify the method of implicit differentiation further.

Assume that we don't know how to differentiate a logarithmic function. Consider then the following problem.

Problem 2

Find the derivative of a function y = ln(x)

Solution

We know the definition of logarithmic function:
y = ln(x) means that
x = e ^y

On the left of the last equality is a function f(x)=x and on the right - a compound function g(x)=e ^y, where y=ln(x), derivative of which we want to calculate.
Let's differentiate both sides of the above expression using the chain rule for compound function e^y:
D_x(x) = D_x(e ^y)
1 = e ^y·D_x(y)
Since e ^y = x by definition of logarithmic function y = ln(x), this results in
1 = x·D_x(y)
from which follows
D_x(y) = 1/x

Hence,
D_x(ln(x)) = 1/x
which is the same as we derived when calculated this derivative directly using the limits.

Problem 3

Find the derivative of a function y = x^sin(x)

Solution

ln(y) = sin(x)·ln(x)
D_x(ln(y)) = D_x(sin(x)·ln(x))
(1/y)·D_x(y) = cos(x)·ln(x) + sin(x)·(1/x)
D_x(y) = y·[cos(x)·ln(x)+sin(x)·(1/x)]
Hence, derivative of x^sin(x)equals to
x^sin(x)·[cos(x)·ln(x)+sin(x)·(1/x)]

Unizor - Derivatives - Function Limit - Extreme Value Theorem

Notes to a video lecture on http://www.unizor.com

Extreme Value Theorem

In this lecture we will consider real functions f(x) of real argument x defined on a closed segment.

We will prove the following theorem.

Extreme Value Theorem

A continuous function defined on a segment (finite interval with endpoints) attains its extreme values.
In other words, there is at least one point within its domain where it reaches its maximum and there is at least one point where it reaches its minimum.

Proof

We will prove this theorem for a case of attaining the maximum value. The corresponding proof for minimum is completely analogous.

The proof is based on the boundedness theorem that states that any continuous function f(x) defined on segment [a,b] is bounded from above and below. It was proven in the previous lecture.

That means that a set of real values of our function {f(x)} is bounded from above. According to the axiom of completeness, there must be the least upper bound for this set of values.
Assume, M is this least upper bound for function f(x) on segment S₁=[a,b]:
∀x∈[a,b] f(x) ≤ M

Consider now a set S₂ of all points x in the domain of our function f(x), where the function value is greater than M−1/2.
This set cannot be empty because in this case M−1/2 would be an upper bound that is smaller than the least upper bound M.

Next, consider set S₃ of all points x in the domain of our function f(x), where the function value is greater than M−1/3.
This set cannot be empty because in this case M−1/3 would be an upper bound that is smaller than the least upper bound M.
In addition, set S₃ is a subset of set S₂ since the restrictions on the values of function f(x) are more strict within this set.

Continue this process with set S₄ of all points x in the domain of our function f(x), where the function value is greater than  M−1/4, set S₅ of all points x in the domain of our function f(x), where the function value is greater than M−1/5 etc.
Generally, set S_n contains all points x in the domain of our function f(x), where the function value is greater than M−1/n.
Each of these sets cannot be empty because in this case M−1/n would be an upper bound that is smaller than the least upper bound M.
Every subsequent set S_n+1 is a subset of the previous set S_n since the restrictions on the values of function f(x) are more strict within this set:
S₁⊃S₂⊃S₃⊃...⊃S_n⊃S_n+1⊃...

Now we can pick a single point from each of these sets to obtain a bounded sequence of points {x_n} within segment[a,b], which, according to Bolzano - Weierstrass theorem should have a convergent subsequence {y_k} with the limit also lying within our closed segment [a,b]. Assume this limit is L.
This limit point L must be the point of maximum for function f(x), that is f(L)=M.

To prove this, consider the following:
Since y_k→L as k→∞ and f(x) is continuous, f(y_k)→f(L).
The distance between f(y_k) and the least upper bound M is an infinitesimal as index k increases to infinity because, if y_k∈S_k, |f(y_k)−M| ≤ 1/k.
Therefore, M must be the limit of f(y_k), that is
M = lim_k→∞f(y_k) = f(L)

As we have proven, the maximum M of function f(x) is attained at point L∈[a,b].

End of proof.

Unizor - Derivatives - Function Limit - Bounded Functions

Notes to a video lecture on http://www.unizor.com

Bounded Functions

In this lecture we will consider real functions f(x) of real argument x.
The domain of these functions will be a contiguous interval, finite or infinite, including or not including the endpoints.
A finite contiguous interval with endpoints included we will call segment.

We will prove the following theorem.

Boundedness Theorem

A continuous function defined on a segment (finite interval with endpoints) is bounded from above and from below.

Proof

The proof is based on two main properties introduced in prior lectures:
(a) Bolzano - Weierstrass Theorem that states that from any bounded sequence we can extract a convergent subsequence.
(b) Continuity property.

We will only prove the boundedness from above, the one from below is completely analogous.

Let's assume the opposite, that our function f(x) is defined and continuous on segment [a,b], and is not bounded from above.
Then for any, however large, number N we will be able to find an argument x_N∈[a,b] such that f(x_N) ≥ N.

The sequence {x_N} consists from points in segment [a,b]and, therefore, is bounded by the endpoints of this segment.
According to Bolzano - Weierstrass Theorem, we can extract from it a subsequence{y_n} of points in this segment that converges to some pointY∈[a,b].
Since a set of values of our function is unbounded on sequence {x_N}, it is also unbounded on subsequence {y_n}and, therefore, there no limit off(y_n) as n→∞.

But function f(x) is continuous on segment [a,b], which means that, if {y_n}→Y∈[a,b], then{f(y_n)}→f(Y). So, the limit off(y_n) does exist.
Came to a contradiction. Hence,f(x) is bounded from above.

Unizor - Derivatives - Limit of Sequence - Bounded Sequence

Notes to a video lecture on http://www.unizor.com

Sequence Limit -
Bounded Sequence

A very important property of bounded sequences (those {x_n}that can be "framed" in upper and lower bounds as A ≤ x_n ≤ Bfor any n) is the following theorem.

Bolzano - Weierstrass Theorem

Any bounded sequence has a convergent subsequence.

Proof

Intuitively, an infinite sequence in a bounded space must have points of accumulation and, therefore, we can pick subsequence that converges to one of these points.
Rigorous proof requires some more precision.

Let's use the method of nested intervals.
Since A ≤ x_n ≤ B for any n, we can state that infinite number of elements of our sequence are in the interval I₁=[A,B].

Split our interval I₁ in two equal parts at midpoint M₁. Since original interval [A,B]has infinite number of members of our sequence, one of its halves or both must also contain an infinite number of them. Assume for definiteness that interval I₂=[A,M₁] is the one with infinite number of members of our sequence. Note that interval I₂ is a subset of interval I₁: I₁⊃I₂.

Split our interval I₂ in two equal parts at midpoint M₂. Since the "parent" interval[A,M₁] has infinite number of members of our sequence, one of its halves or both must also contain an infinite number of them. Assume for definiteness that interval I₃=[M₂,M₁] is the one with infinite number of members of our sequence. Note that interval I₃ is a subset of interval I₂: I₂⊃I₃.

This process of splitting intervals produces an infinite sequence of nested intervals:
I₁⊃I₂⊃I₃⊃...⊃I_k⊃I_k+1⊃...
Each subsequent interval is half the size of a previous interval and infinite number of members of our original sequence {x_n} is located in each of them.

Let's choose any one point y_kfrom each I_k. We will prove that this subsequence {y_k} of the original sequence {x_n}converges to some point inside interval [A,B].

Consider the left end of each of these intervals. Since intervals are nested, these left ends produce the monotonically increasing sequence of real numbers bounded from above by point B and, therefore, have a limit - point L₁. This had been proven in "Algebra - Limits - Theoretical Problems" lecture of this course.
Similarly, consider the right end of each of these intervals. Since intervals are nested, these right ends produce the monotonically decreasing sequence of real numbers bounded from below by point A and, therefore, have a limit - point L₂.
Since the length of our nested intervals converges to zero, it is obvious that points L₁ and L₂coincide. Let's call this one point L.

This point L is the also the limit of our subsequence {y_k}because this subsequence is bounded from below by left ends of our nested intervals, bounded from above by their right ends, and these two bounding sequences of left and right ends converge to the same limit L. This had been proven in "Algebra - Limits - Theoretical Problems" lecture of this course.

End of proof.

Unizor - Combinatorics - Problem 2.9 - Vandermonde Identity

https://youtu.be/fxrut5Rbke0


Notes to a video lecture on http://www.unizor.com

Advanced Combinatorics - Problems 2.9.

Try to solve these problems yourself and check against the answers that immediately follow each problem.

Problem 1 - Vandermonde's identity

Prove the following identity for any natural numbers m, n and r(where r ≤ m+n):
C_m+n^r = Σi∈[0,r]C_mⁱ·C_n^r−i

Logic 1 (combinatorial):

Imagine, you have to pick a group of r people from a set of m men and n women.
One obvious answer is direct usage of the formula for a number of combinations of r objects from m+n objects, regardless of men/women composition in the group. The answer in this case is C_m+n^r, which is exactly an expression on the left of Vandermonde's identity.

On the other hand, we can differentiate groups by the number of men in them.
There are certain number of groups of r people with 0 men (and, correspondingly, r−0 women),
Then there are some groups with 1 man (and, correspondingly, r−1 women).
Some groups will have 2 men (and, correspondingly, r−2 women).
etc.
Some groups would have r−1 men (and, correspondingly, 1 woman).
Finally, some groups will haver men (and, correspondingly, 0 women).

The number of groups counted separately by the number of men and women should be equal to the number C_m+n^r for the total number of groups we came up with counting them without regard to men/women composition.

Let's determine now how many groups can be chosen with exactly i men (and, correspondingly, r−i women) for each i from 0 to r and sum them up to get a total of groups of r people.
The number of groups of i men out of all m men is C_mⁱ.
To each of these groups of i(out of m) men we can add any group of r−i (out of n) women (there are C_n^r−i of them). So, the total number of groups composed of i men and r−i women equals to
C_mⁱ·C_n^r−i

Summarizing this by the number of men in a group i from 0 to r, we should get the total number of groups C_m+n^rof r people out of all m+n available that we calculated in the beginning:
Σi∈[0,r]C_mⁱ·C_n^r−i

The above is the right side of the Vandermonde's identity.
End of proof.

Logic 2 (algebraic):

We will use Newton's binomial formula
(a+b)^k = Σi∈[0,k]C_kⁱ·a^k−i·bⁱ

Let's use it for the following three cases.
(a) a=1, b=x, k=m:
(1+x)^m = Σi∈[0,m]C_mⁱ·xⁱ
(b) a=1, b=x, k=n:
(1+x)ⁿ = Σi∈[0,n]C_nⁱ·xⁱ
(c) a=1, b=x, k=m+n:
(1+x)^m+n = Σi∈[0,m+n]C_m+nⁱ·xⁱ

From obvious identity
(1+x)^m+n = (1+x)^m·(1+x)ⁿ
we derive the corresponding equality between
Σi∈[0,m+n]C_m+nⁱ·xⁱ
and the product of
Σi∈[0,m]C_mⁱ·xⁱ by
Σi∈[0,n]C_nⁱ·xⁱ

The first one is a polynomial of(m+n)^th power. The second is a product of a polynomial of m^th power by a polynomial of n^th power, which is, in theory, also a polynomial of (m+n)^th power. So, since they are equal for any argument x, their coefficients atx at any particular power (from 0^th to (m+n)^th) should be the same.

The coefficients of the first polynomial are explicitly participating in the expression. Namely, for any r∈[0,m+n] a coefficient at x^r equals to C_m+n^r.

Since we have to compare this with a coefficient of a product of two polynomials of powers m and n with known coefficients, we have to come up with a coefficient of a product of two polynomials expressed in terms of coefficients of each one of them.
To obtain x^r from a product of two polynomials, we can
take x⁰ from the first and x^rfrom the second (with their corresponding coefficients C_m⁰and C_n^r) AND
take x¹ from the first and x^r−1from the second (with their coefficients C_m¹ and C_n^r−1) AND
take x² from the first and x^r−2from the second (with their coefficients C_m² and C_n^r−2) AND etc.
take x^r−1 from the first and x¹from the second (with their coefficients C_m^r−1 and C_n¹) AND, finally,
take x^r from the first and x⁰from the second (with their coefficients C_m^r and C_n⁰)
and sum up all of these results getting x^r with a coefficient
Σi∈[0,r]C_mⁱ·C_n^r−i
This coefficient at x^r of the product of two polynomials(1+x)^m and (1+x)ⁿ should be equal to a coefficient C_m+n^r at x^r of the polynomial 1+x)^m+n.
That proves Vandermonde's identity.