Order of Expression: c,m,logm,2^j-1/2, m^o(logm) Explained

[bincy]

Hii Every one,

In one paper I read that, [math]{\displaystyle \sum_{j\geq1}\left(\frac{c*m*logm}{2^{\left(\frac{j-1}{2}\right)}}\right)}^{j}<=m^{o(logm)}
[/math] with the explanation "Since the sum is of the same order as its largest term".

c>0, m>=2. m is an integer.
Can anyone pls explain?Regards,
Bincy

 

[CaptainBlack]

Hii Every one,

In one paper I read that, [math]{\displaystyle \sum_{j\geq1}K \left(\frac{c*m*logm}{2^{\left(\frac{j-1}{2}\right)}}\right)}^{j}<=m^{o(logm)}
[/math] with the explanation "Since the sum is of the same order as its largest term".

c>0, m>=2. m is an integer.
Can anyone pls explain?Regards,
Bincy

If we accept that the sum is of the same order as its largest term (and this is ambiguous since order in this context is poorly defined) then you need to find the largest term, or at least a bound on it. What I think it is trying to say is that for \(m\) large enough, there exists a \(K>0\) such that:

\[{ \sum_{j\geq1}\left( \frac{c\;m\;\log(m)}{2^{\left(\frac{j-1}{2}\right)}}\right)}^{j} \le K {\left(\frac{c \; m\; \log(m) }{2^{\left( \frac{J-1}{2}\right)}}\right)}^{J}\]

where the right hand side is the largest term.

Do this by finding the \(x\) that maximises:

\[f(x)=\left[ \frac{c\;m\;\log(m)}{2^{\frac{x-1}{2}}}\right]^x \]

and using the function value at this point as a bound on the largest term.

(to me it looks like the leading term is always the largest in this case)

CB

 

[CaptainBlack]

If we accept that the sum is of the same order as its largest term (and this is ambiguous since order in this context is poorly defined) then you need to find the largest term, or at least a bound on it. What I think it is trying to say is that for \(m\) large enough, there exists a \(K>0\) such that:

\[{ \sum_{j\geq1}\left( \frac{c\;m\;\log(m)}{2^{\left(\frac{j-1}{2}\right)}}\right)}^{j} \le K {\left(\frac{c \; m\; \log(m) }{2^{\left( \frac{J-1}{2}\right)}}\right)}^{J}\]

where the right hand side is the largest term.

Do this by finding the \(x\) that maximises:

\[f(x)=\left[ \frac{c\;m\;\log(m)}{2^{\frac{x-1}{2}}}\right]^x \]

and using the function value at this point as a bound on the largest term.

(to me it looks like the leading term is always the largest in this case)

CB

So the leading term is dominant and is for some \(K\) may be written:

\[f(m)=K m \log(m)\]

so to get the result we need to show that for \(m\) large enough:

\[f(m)\le m^{o(\log(m)} \]

which reduces to:

\[\frac{\log(f(m))}{m}\le o(\log(m))\]

which if we show that:

\[ \lim_{m\to \infty} \frac{\log(f(m))}{m \log(m)} = 0 \]

we are done.

Putting \(x=K m\log(m)\) the limit on the right becomes becomes:

\[ K \lim_{x\to \infty} \frac{\log(x)}{x}\]

which is well known to be \(0\)

CB

 

[CaptainBlack]

In an earlier post in this thread I wrote:

If we accept that the sum is of the same order as its largest term (and this is ambiguous since order in this context is poorly defined) then you need to find the largest term, or at least a bound on it.

The reader should have noted the equivocation in the first part of this. That is because the claim that the sum is of the same order as its largest term is not in general true and would have to be proven for what follows in the earlier posts to hold (allowing for the noted ambiguity in the term "order").

One way to show this is to consider the integral analogue of this via the integrals:

\[ I(\sigma)= \int_0^{\infty} \frac{1}{\sqrt{2\pi} \sigma}e^{- \; \frac{x^2}{2\sigma^2}}\;dx \]

Here the analogue of the largest term is the maximum value of the integrand \(\frac{1}{\sqrt{2 \pi} \sigma}\), but \(I(\sigma)=\frac{1}{2} \notin O(\sigma^{-1})\) or \(o(\sigma^{-1}) \) for that matter.

Note the analogy can be elliminated by considering the series with \(n\)-th term the integral from \(n-1\) to \(n\), then \(I(\sigma)\) is the sum of a series with the properties required of a counter example.

CB