Proof that a function is of exponential order


by awelex
Tags: exponential, function, order, proof
awelex
awelex is offline
#1
Jul19-11, 03:23 AM
P: 44
Hi,

I'm being asked to test whether a function is of exponential order, i.e. whether

abs( f(x) ) <= M*exp(a * t), for all t >= T (which is finite).

The function is x * ln( x ).

Now, I have the solution right here, so I know how to solve it. However, I did it a different way and wanted to ask if it is valid as well. Here it goes:

First, observe that ln( x ) < x for large x, because

ln( x ) grows that a slower rate than x.

Therefore,

abs(x * ln( x )) <= x^2.

If we can show that x^2 is of exponential order, then we have also shown that x * ln( x ) is of exponential order.

x^2 = exp( 2 * ln( x )), which is clearly of exponential order.


I think the problem with this approach is the step where I show that ln( x ) < x for large x. I know that that is right by intuition and by looking at the graphs, but I don't think that I've proved it properly. I'm sure it is not enough to prove that one function grows slower than the other (i.e. that one derivative is always smaller than the other after a certain value). How do I proof this in a rigorous way?

Thanks,

Alex

EDIT: How about the following: after x = 1, ln( x ) grows slower than x. But since ln( 1 ) < 1, it follows that after x=1 ln( x ) will always be less than x (probably even before that). Is that good enough?
Phys.Org News Partner Mathematics news on Phys.org
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
disregardthat
disregardthat is offline
#2
Jul19-11, 04:25 AM
Sci Advisor
P: 1,704
Take the function f(x) = x-log(x) for x >= 2. the derivative is 1-1/x, which is positive. If f(x) = 0 for any x >= 2, rolles theorem says that f'(c) = 0 for some c between 2 and x. This is impossible, and since e.g. f(e) = e-1 > 0, the intermediate value theorem implies that f(x) must always be positive, and hence that x > log(x) for all x >= 2.

I used 2 and e as arbitrary constants a and b such that 1<a and 1<b to ensure that the derivative is positive, and without having to prove that 2 > log(2).
LCKurtz
LCKurtz is offline
#3
Jul19-11, 03:15 PM
HW Helper
Thanks
PF Gold
LCKurtz's Avatar
P: 7,221
Or a direct way:

[tex]\frac 1 t < 1 \hbox{ if } t>1[/tex]
[tex]\int_1^x\frac 1 t\,dt < \int_1^x 1\,dt[/tex]
[tex]\ln(x)-\ln(1) < x-1[/tex]
[tex]\ln(x)<x-1<x[/tex]

HallsofIvy
HallsofIvy is offline
#4
Jul19-11, 03:46 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,894

Proof that a function is of exponential order


Quote Quote by awelex View Post
Hi,

I'm being asked to test whether a function is of exponential order, i.e. whether

abs( f(x) ) <= M*exp(a * t), for all t >= T (which is finite).
This is incorrect. It should be "[itex]|f(x)|\le M exp(ax)[/itex] for all [itex]x\ge X[/itex]". You can't change variables.

The function is x * ln( x ).

Now, I have the solution right here, so I know how to solve it. However, I did it a different way and wanted to ask if it is valid as well. Here it goes:

First, observe that ln( x ) < x for large x, because

ln( x ) grows that a slower rate than x.
Yes, that is true.

Therefore,

abs(x * ln( x )) <= x^2.

If we can show that x^2 is of exponential order, then we have also shown that x * ln( x ) is of exponential order.

x^2 = exp( 2 * ln( x )), which is clearly of exponential order.
No, exp(2 ln(x)) is NOT of exponential order. It is of the form "[itex]Me^{af(x)}[/itex]" where M= 1, a= 2, and f(x)= ln(x) but that is NOT of the form "[itex]Me^{ax}[/itex]". You cannot just insert a (slowly increasing) nfunction of x in place of x itself.


I think the problem with this approach is the step where I show that ln( x ) < x for large x. I know that that is right by intuition and by looking at the graphs, but I don't think that I've proved it properly. I'm sure it is not enough to prove that one function grows slower than the other (i.e. that one derivative is always smaller than the other after a certain value). How do I proof this in a rigorous way?

Thanks,

Alex

EDIT: How about the following: after x = 1, ln( x ) grows slower than x. But since ln( 1 ) < 1, it follows that after x=1 ln( x ) will always be less than x (probably even before that). Is that good enough?
Your fundamental problem is NOT if this is "good enough". Your fundamental problem is that you are trying to prove that xln(x) is of exponential order and it is NOT.

In fact, you have shown that xln(x) increases more slowly than [itex]x^2[/itex] which is NOT of exponential order itself.
LCKurtz
LCKurtz is offline
#5
Jul19-11, 04:33 PM
HW Helper
Thanks
PF Gold
LCKurtz's Avatar
P: 7,221
Quote Quote by HallsofIvy View Post
In fact, you have shown that xln(x) increases more slowly than [itex]x^2[/itex] which is NOT of exponential order itself.
Either I'm too drunk to read what you said or you don't mean that.

x2<ex for (even not very) large x.
HallsofIvy
HallsofIvy is offline
#6
Jul19-11, 07:52 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,894
Confusion as to exactly what "of exponential order" meant- does the function increase at the same rate as [itex]Me^{kx}[/itex] for some M and k or just not as fast. I see now that we are talking about the second here.


Register to reply

Related Discussions
Bessel function Solution to Second order ODE with exponential coefficient Calculus & Beyond Homework 4
Third Order DE Using Complex Exponential Advanced Physics Homework 7
First order DE with exponential Differential Equations 3
high order derivitative of exponential function Calculus 4
2nd order with exponential and constant on right side Differential Equations 4