Saturday, February 07, 2009

Derivative of Increasing and Decreasing Functions

Lemma: Derivative of Increasing and Decreasing Functions

Let f be a continuous function on (a,b) where the at no point f'(x)=0.

If for all x on [a,b], f(x) is increasing, then f'(x) is positive.

If for all x on [a,b], f(x) is decreasing, then f'(x) is negative.

Proof:

(1) From the definition of derivatives (see Definition 1, here):

f'(x) = lim (Δx → 0) [f(x + Δx) - f(x)]/(Δx)

So, the sign of f'(x) is the sign of [f(x + Δx) - f(x)]/Δx and we can assume that is is nonzero.

(2) Case I: Δx is positive

If f(x) is strictly increasing, then f(x + Δx) - f(x) is positive and f'(x) is positive.

If f(x) is striclty decreasing, then f(x + Δx) - f(x) is negative and f'(x) is negative.

(3) Case II: Δx is negative

If f(x) is strictly increasing, then f(x + Δx) - f(x) is negative and f'(x) is positive

If f(x) is strictly decreasing, then f(x + Δx) - f(x) is positive and f'(x) is negative.

QED

Tuesday, February 03, 2009

An Inequality Lemma for the Cauchy Bound of Real Roots

The following result is used my proof of Cauchy's Bound for real roots.

Lemma 1: abs(c)
n = abs(cn)

Proof:

(1) Assume that c is nonnegative

(2) Then, cn is nonnegative

(3) Then, abs(cn) = cn

(4) Since abs(c) = c, it follows that: cn = abs(c)n

(5) Assume that c is negative

(6) We can assume that n is odd

[Otherwise, cn = (-c)n = abs(c)n = abs(cn) ]

(8) abs(cn) = -cn = (-1)n*cn = (-c)n = abs(c)n

QED

Lemma 2:

Let:

ancn = -an-1cn-1 + .... + -a0

Then:

abs(an)*abs(c)n ≤ abs(an-1)*abs(c)n-1 + ... + abs(a0)

Proof:

(1) Using the Triangle Inequality (see Lemma 4, here), we know that:

abs(-an-1cn-1 + .... + -a0) ≤ abs(-an-1cn-1) + ... + abs(-a0)

so that:

abs(ancn) ≤ abs(-an-1cn-1) + ... + abs(-a0)

(2) Using a basic property of inequalities (see Lemma 1, here):

abs(an)*abs(cn) = abs(ancn)

and likewise:

abs(-an-1)*abs(cn-1) = abs(-an-1cn-1)

...

(3) So we have:

abs(an)*abs(cn) ≤ abs(-an-1)*abs(cn-1) + ... + abs(-a0)

(4) Using Lemma 1 above, we have:

abs(an)*abs(c)n ≤ abs(an-1)*abs(c)n-1 + ... + abs(a0)

QED

Triangle Inequality

Definition 1: Absolute Value

abs(a) = a if a is nonnegative or abs(a)=-a if a is negative.

So for example:

abs(5) = 5

abs(0) = 0

abs(-1) = 1

Now, let's look at some basic properties

Lemma 1: abs(ab) = abs(a)*abs(b)

Proof:

Case I: both a,b positive

abs(ab) = ab = abs(a)*abs(b)

Case II: both a,b negative

abs(ab) = ab = (-a)*(-b) = abs(a)*abs(b)

Case III: one negative, one positive

Assume a is positive, b is negative (since a,b are symmetrical, we can switch them as necessary)

abs(ab) = -ab = a*(-b) = abs(a)*abs(b)

QED

Lemma 2: -abs(a) ≤ a ≤ abs(a)

Proof:

Case I: a is nonnegative

-a ≤ a ≤ a

so

-abs(a) ≤ a ≤ abs(a)

Case II: a is negative

a ≤ a ≤ -a

so

-abs(a) ≤ a ≤ abs(a)

QED

Lemma 3: abs(a) ≤ b if and only if -b ≤ a and a ≤ b.

Proof:

(1) Assume abs(a) ≤ b

Case I: a is nonnegative

abs(a) = a

Since abs(a) ≤ b, it follows that a ≤ b and b is nonnegative

Since b is nonnegative and a is nonnegative, then it -b ≤ a.

Case II: a is negative

Since abs(a) ≤ b, it follows that -a ≤ b which is the same as -b ≤ a and therefore b must be nonnegative.

Since b is nonnegative, it follows that a ≤ b.

(2) Assume that -b ≤ a and a ≤ b.

Case I: a is nonnegative

Since a ≤ b, it follows that b is nonnegative

So abs(a) ≤ b.

Case II: a is negative

Since -b ≤ a, it follows that b ≥ -a.

Since a is negative, -a is positive, and we have:

abs(a) ≤ b.

QED

Lemma 4: Triangle Inequality

For all real numbers a,b

abs(a + b) ≤ abs(a) + abs(b)

Proof:

(1) For all real numbers a,b (from Lemma 1 above)

-abs(a) ≤ a ≤ abs(a)

-abs(b) ≤ b ≤ abs(b)

(2) Adding these two conditions together gives us:

-[abs(a) + abs(b)] ≤ a + b ≤ abs(a) + abs(b)

(3) Let c = a+b and d =abs(a) + abs(b)

(4) Using Lemma 3, we know that:

abs(c) ≤ d if and only if -d ≤ c and c ≤ d.

(5) But using step #2, we know that:

-d = -[abs(a) + abs(b)] ≤ c = a + b

and

c = a + b ≤ d = abs(a) + abs(b)

(6) So, using step #4 we get:

abs(c) ≤ d

which is equivalent to:

abs(a + b) ≤ abs(a) + abs(b)

QED

Sunday, February 01, 2009

Polynomials are continuous

For a definition of polynomials, see Definition 1, here. For a definition of continuous functions, see Definition 1, here.

Lemma 1: f(x)=x is continuous

Proof:

(1) Let ε be any arbitrary value.

(2) Let δ = ε

(3) For any point c, it is clear that if x lies in (c - δ, c + δ), then f(x)=x lies in (f(c) - ε, f(c) + ε )

QED

Corollary 1.1 : Polynomials are continuous

Proof:

(1) The function f(x)=x is continuous. [See Lemma 1 above]

(2) Since the product of continuous functions is continuous [See Lemma 3, here], then f(x)=xn where n is a positive integer is also continuous.

(3) Since f(x)=C is continuous [See Lemma 1, here], it follows that any function of the form cxn is also continuous.

(4) Since the addition of continuous functions is continuous [See Lemma 2, here], it follows that any polynomial function is continuous since it consists of the form:

f(x) = c0 + c1x + c2x2 + ... + cnxn

where each ci is a constant.

QED

Lemma 2: The Derivative of a polynomial is itself a polynomial

Proof

(1) The derivative of each term of a polynomial is itself a term of a polynomial [See the Lemma 2, here]

(2) So, it follows that the derivative itself is also a polynomial. [See Definition 1, here]

QED

Corollary 2.1: The derivative of a polynomial is a continuous function.

Proof:

This follows directly from Lemma 2 above and Corollary 1.1 above.

QED

Interval of a Function with Simple Roots

Lemma: Interval of a Function with Simple Roots

Let f be a function with simple roots such that f(c)=0

Then there exists an interval (a,b) such that:

c is in (a,b)

for all x in (a,b), f'(x) is all positive or all negative

Proof:

(1) Since f has only simple roots and f(c)=0, then it follows that f'(c) ≠ 0. [See Corollary 1.1, here]

(2) Since f is a polynomial, we know that f'(x) is continuous. [See Corollary 2.1, here]

(3) Since f'(c) is nonzero, let ε be nonzero and less than abs{ f'(c) }.

(4) Since f'(x) is continuous at c, there exists a number δ such that if x is in the (c - δ, c + δ), then f'(x) is in (f'(c)-ε, f'(c)+ε). [By the definition of a continuous function]

(5) Since ε is less than abs{f'(c) }, it follows that for x in (c -δ, c + δ), f'(x) is either entirely positive or entirely negative.

QED