Proof that a function is of exponential order

In summary: We are not talking about the first. In summary, the conversation is discussing how to prove that the function x * ln(x) is of exponential order. One approach is to show that it is always less than x^2, which is of exponential order itself, but this approach is not sufficient. Another approach is to show that after x=1, ln(x) always grows slower than x, but there is uncertainty about whether this proof is rigorous enough. Ultimately, it is determined that x * ln(x) is not of exponential order, but rather increases more slowly than x^2.
  • #1
awelex
44
0
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?
 
Last edited:
Mathematics news on Phys.org
  • #2
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).
 
  • #3
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]
 
  • #4
awelex said:
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.
 
  • #5
HallsofIvy said:
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.
 
  • #6
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.
 

1. What does it mean for a function to be of exponential order?

A function is said to be of exponential order if it can be bounded by an exponential function at infinity. This means that as the input of the function gets larger and larger, the output of the function grows at a rate that is proportional to an exponential function. In other words, the function's growth rate is similar to that of an exponential function.

2. How can I prove that a function is of exponential order?

There are a few different methods for proving that a function is of exponential order. One common method is to use the limit comparison test, where you compare the function to a known exponential function and take the limit as the input approaches infinity. Another method is to use the definition of exponential order and show that the function's growth rate is indeed bounded by an exponential function at infinity.

3. What are some properties of functions that are of exponential order?

Functions that are of exponential order have some common properties, such as a constant growth rate at infinity and an unbounded growth rate as the input approaches infinity. They also have a characteristic shape, with a steep initial increase followed by a gradual flattening of the curve.

4. Are all exponential functions automatically of exponential order?

No, not all exponential functions are of exponential order. For a function to be of exponential order, it must have a bounded growth rate at infinity, which is not always the case for exponential functions. Functions that have a growth rate that is faster than an exponential function at infinity are not considered to be of exponential order.

5. Can a function be of exponential order at some points and not at others?

Yes, a function can be of exponential order at some points and not at others. This is because the definition of exponential order only applies at infinity, so a function can exhibit exponential growth at some points but not be of exponential order overall. It is important to consider the behavior of a function at infinity when determining if it is of exponential order.

Similar threads

Replies
4
Views
283
Replies
1
Views
744
  • Calculus and Beyond Homework Help
Replies
10
Views
1K
Replies
3
Views
699
  • Calculus and Beyond Homework Help
Replies
9
Views
688
  • Precalculus Mathematics Homework Help
Replies
12
Views
938
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
13
Views
635
Replies
3
Views
2K
Back
Top