Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.

learn more… | top users | synonyms (1)

25
votes
1answer
853 views

How does $ \sum_{p<x} p^{-s} $ grow asymptotically for $ \text{Re}(s) < 1 $?

Note the $ p < x $ in the sum stands for all primes less than $ x $. I know that for $ s=1 $, $$ \sum_{p<x} \frac{1}{p} \sim \ln \ln x , $$ and for $ \mathrm{Re}(s) > 1 $, the partial sums ...
11
votes
1answer
2k views

Derivation of asymptotic solution of $\tan(x) = x$.

An equation that seems to come up everywhere is the transcendental $\tan(x) = x$. Normally when it comes up you content yourself with a numerical solution usually using Newton's method. However, ...
4
votes
4answers
700 views

Simple proof of showing the Harmonic number $H_n = \Theta (\log n)$

Consider the partial sum of the divergent Harmonic series $H_n = \sum\limits_{k = 1}^{n}\frac{1}{k}$. I recently saw a question which required finding out the asymptotic bounds of $H_n$. Now, I could ...
15
votes
3answers
1k views

How do you prove that $n^n$ is $O(n!^2)$?

It seems obvious that: $$n^n \in O(n!^2)$$ But I can't seem to find a good way to prove it.
11
votes
2answers
350 views

Laplace's method

I'm still having a little trouble applying Laplace's method to find the leading asymptotic behavior of an integral. Could someone help me understand this? How about with an example, like: ...
9
votes
2answers
498 views

Showing that $\lim_{n\to\infty}\sum^n_{k=1}\frac{1}{k}-\ln(n)=0.5772\ldots$

How to show that $$\lim_{n\to\infty}\sum^n_{k=1}\frac{1}{k}-\ln(n)=0.5772\ldots$$ No clue at all. Need help! Appreciated!
12
votes
3answers
823 views

Euler's Constant: The asymptotic behavior of $\left(\sum\limits_{j=1}^{N} \frac{1}{j}\right) - \log(N)$

I want to show that there exists a constant $C\in\mathbb{R}$ such that $$ \sum_{j=1}^N \frac1{j} = \log(N)+C+O(1/N). $$ I know how to prove that the Euler-Mascheroni constant exists (which I ...
18
votes
2answers
506 views

Asymptotic behaviour of sums of consecutive powers

Let $S_k(n)$, for $k = 0, 1, 2, \ldots$, be defined as follows $$S_k(n) = \sum_{i=1}^n \ i^k$$ For fixed (small) $k$, you can determine a nice formula in terms of $n$ for this, which you can then ...
10
votes
3answers
538 views

How does Lambert's W behave near ∞?

How does $W$ behave near $+\infty$ compared to $\log$? In particular, I'm interested in the asymptotic expansion of $$\frac{W(x)}{\ln(x)}$$ near $\infty$ (but along the positive real line, if that ...
10
votes
5answers
594 views

Bounding the integral $\int_{2}^{x} \frac{\mathrm dt}{\log^{n}{t}}$

If $x \geq 2$, then how do we prove that $$\int_{2}^{x} \frac{\mathrm dt}{\log^{n}{t}} = O\Bigl(\frac{x}{\log^{n}{x}}\Bigr)?$$
5
votes
1answer
1k views

Asymptotics for a partial sum of binomial coefficients

Good afternoon, I would like to ask, if anyone knows how to evaluate a sum $$\sum_{k=0}^{\lambda n}{n \choose k}$$ for fixed $\lambda < 1/2$ with absolute error $O(n^{-1})$, or better. In ...
4
votes
4answers
251 views

Determine whether $F(x)= 5x+10$ is $O(x^2)$

Please, can someone here help me to understand the Big-O notation in discrete mathematics? Determine whether $F(x)= 5x+10$ is $O(x^2)$
26
votes
2answers
1k views

What are the rules for equals signs with big-O and little-o?

This question is about asymptotic notation in general. For simplicity I will use examples about big-O notation for function growth as $n\to\infty$ (seen in algorithmic complexity), but the issues that ...
14
votes
6answers
3k views

Stirling's formula: proof?

Suppose we want to show that $$ n! \sim \sqrt{2 \pi} n^{n+(1/2)}e^{-n}$$ Instead we could show that $$\lim_{n \to \infty} \frac{n!}{n^{n+(1/2)}e^{-n}} = C$$ where $C$ is a constant. Maybe $C = ...
8
votes
2answers
636 views

Approximation of Products of Truncated Prime $\zeta$ Functions

The problem arose, while I was looking at products of power prime zeta functions $$ P_x(ks)=\sum_{p\,\in\mathrm{\,primes}\leq x} p^{-ks}, $$ with $k\in \mathbb{N}$ and $s=it$ with real $t$. By using ...
1
vote
3answers
399 views

big and small O notation help

I was hoping someone could help me answer this question. I can't wrap my head around this concept: Why is $\cal{O}(x^3) = o(x^2)$?
7
votes
1answer
262 views

Bounds on $\sum_{k=0}^{m} \binom{n}{k}x^k$ and $\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}, m<n$

I've read this interesting article by Woersch (1994) dealing with approximation of binomial coefficients (rows of Pascal's triangle). I'm just wondering if similar bounds exist for partial binomial ...
1
vote
2answers
122 views

Solving the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n)$

Please help me solve the recurrence $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n) $$
20
votes
2answers
747 views

Proof $\sum\limits_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} +O\left(\frac1{\log^2 n}\right)$

More precisely, $$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} -\frac{\pi^2 + 6 \gamma^2}{12 \log^2 n} +O\left(\frac1{\log ^3 n}\right).$$ This is Theorem 4 ...
14
votes
2answers
533 views

Asymptotics of sum of binomials

How can you compute the asymptotics of $$S=n + m - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+m-k}}{n^{n+m-1}}\;?$$ We have that $n \geq m$ and $n,m \geq 1$. A simple application of ...
13
votes
4answers
436 views

Large $n$ asymptotic of $\int_0^\infty \left( 1 + x/n\right)^{n-1} \exp(-x) \, \mathrm{d} x$

While thinking of 71432, I encountered the following integral: $$ \mathcal{I}_n = \int_0^\infty \left( 1 + \frac{x}{n}\right)^{n-1} \mathrm{e}^{-x} \, \mathrm{d} x $$ Eric's answer to the linked ...
21
votes
9answers
3k views

What is the purpose of Stirling's approximation to a factorial?

Stirling approximation to a factorial is $$ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n. $$ I wonder what benefit can be got from it? From computational perspective (I admit I don't ...
17
votes
2answers
726 views

A (non-artificial) example of a ring without maximal ideals

As a brief overview of the below, I am asking for: An example of a ring with no maximal ideals that is not a zero ring. A proof (or counterexample) that $R:=C_0(\mathbb{R})/C_c(\mathbb{R})$ is a ...
23
votes
2answers
765 views

How to show that $\sum\limits_{k=1}^{n-1}\frac{k!k^{n-k}}{n!}$ is asymptotically $\sqrt{\frac{\pi n}{2}}$?

According to "Concrete Mathematics" on page 434, elementary asymptotic methods show that $\displaystyle \sum_{k=1}^{n-1}\frac{k! \; k^{n-k}}{n!}$ is asymptotically $\sqrt{\frac{\pi n}{2}}$. Does ...
20
votes
5answers
687 views

Asymptotics of $1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1$

Suppose $n\in\mathbb{Z}$ and $n > 0$. Let $$H_n = 1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1.$$ I would like to find a Big O bound for $H_n$. A Big $\Theta$ result would be even better.
19
votes
2answers
997 views

please solve a 2013 th derivative question?

$ f(x) = 6x^7\sin^2(x^{1000}) e^{x^2} $ Find $ f^{(2013)}(0) $ A math forum friend suggest me to use big O symbol, however have no idea what that is, so how does that helping?
8
votes
0answers
144 views

Let $x_n$ be the (unique) root of $\Delta f_n(x)=0$. Then $\Delta x_n\to 1$

Note that by Cesaro's Theorem, we have as a consequence $$\frac{x_n}n\to 1$$ Consider $$r_n(x)=e^{-x}-\sum_{k=0}^n (-1)^k\frac{x^k}{k!}$$ and $$f_n(x)=(-1)^{n+1}e^{-x}r_n(x)$$ One can argue by ...
8
votes
2answers
1k views

Compactly supported function whose Fourier transform decays exponentially?

It's well known now that a function can not be compactly supported both on the space side and the frequency side (so-called uncertainty principle). On the other hand a function can have exponential ...
1
vote
1answer
173 views

An issue with approximations of a recurrence sequence

By trying to give an approximation to a given recurrence sequence I encountered a problem. To be more precise I have a method but it fails if the right condition is not met and I wonder how I should ...
7
votes
1answer
178 views

Asymptotic formula for almost primes

I have developed a formula for almost primes which is far more accurate asymptotically than Landau's well known $$\pi_k(n) \sim \left( \frac{n}{\log n} \right) \frac{(\log\log n)^{k-1}}{(k - 1)!}$$ ...
3
votes
1answer
203 views

Series about Euler-Maclaurin formula

The Euler-Maclaurin formula says (from Concrete Mathematics section 9.5) \[ \sum_{a\le{}k< b}f(k)=\int_a^bf(x)dx+\left.\sum_{k=1}^m\frac{B_k}{k!}f^{(k-1)}(x)\right|_a^b+R_m \] where ...
3
votes
2answers
393 views

Sum of cubes of binomial coefficients

I reduced a homework problem in combinatorics to giving an asymptotic estimate for $\sum_{k=0}^n{n \choose k}^3$. I assume Stirling's approximation can help, but I'm not experienced with making ...
2
votes
1answer
276 views

Asymptotic error of Fourier series partial sum of sawtooth function

In Iwaniec's book, Topics in Classical Automorphic Forms, pg. 4, he gives the statement: $$\{x\}=\frac{1}{2}-\sum_{n=1}^N\frac{\sin 2\pi nx}{\pi n}+O((1+||x||N)^{-1})$$ where $\{x\}$ denotes the ...
1
vote
0answers
96 views

how many ways to make change, asymptotics

This is a simplified coin-changing question. Suppose the only coins available are all powers of $10$ dollars. How many ways are there to make change for $\$ 1000000$? In general, to make change for ...
0
votes
1answer
625 views

Dominant term and Big Omega

For the given expression, determine the dominant term and then use the dominant term to classify the algorithm in big-O terms and also in $\Omega$-notation. $$n^3+n^2\log_2(n)+n^3\log_2(n)$$ So, I ...
157
votes
3answers
7k views

How many fours are needed to represent numbers up to $N$?

The goal of the four fours puzzle is to represent each natural number using four copies of the digit $4$ and common mathematical symbols. For example, $165=(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}}}) ...
21
votes
3answers
3k views

Prove that this function is bounded

This is an exercise from Problems from the Book by Andreescu and Dospinescu. When it was posted on AoPS a year ago I spent several hours trying to solve it, but to no avail, so I am hoping someone ...
10
votes
4answers
361 views

Singular asymptotics of Gaussian integrals with periodic perturbations

At the bottom of page 5 of this paper by Giedrius Alkauskas it is claimed that, for a $1$-periodic continuous function $f$, $$ \int_{-\infty}^{\infty} f(x) e^{-Ax^2}\,dx = \sqrt{\frac{\pi}{A}} ...
9
votes
1answer
254 views

What is a good asymptotic for $f_n = f_{n-1}+\ln(f_{n-1})$?

Let $f_0=2$ and $f_n=f_{n-1}+\ln(f_{n-1})$. What is a good asymptotic to the sequence $f_n$? With good I mean much better than $f_n \sim \dfrac{3n \ln(2)\ln(n)}{2}$.
5
votes
2answers
497 views

Limit of $S(n) = \sum_{k=1}^{\infty} \left(1 - \prod_{j=1}^{n-1}\left(1-\frac{j}{2^k}\right)\right)$ - Part II

This is a follow up of Limit of $S(n) = \sum_{k=1}^{\infty} \left(1 - \prod_{j=1}^{n-1}\left(1-\frac{j}{2^k}\right)\right)$ More details can be found in the above thread. Let $S(n) = \displaystyle ...
13
votes
3answers
439 views

Order of the smallest group containing all groups of order $n$ as subgroups.

Let $n\in \Bbb N$ be fixed and $m\in \Bbb N$ be the least number such that there exists a group of order $m$ in which all groups of order $n$ can be (isomorphically) embedded. Can we deduce $n!=m$?
11
votes
6answers
394 views

Asymptotic behaviour of a multiple integral on the unit hypercube

A few days ago I found an interesting limit on the "problems blackboard" of my University: $$\lim_{n\to +\infty}\int_{(0,1)^n}\frac{\sum_{j=1}^n x_j^2}{\sum_{j=1}^n x_j}d\mu = 1.$$ The correct claim, ...
10
votes
3answers
266 views

Estimate $\displaystyle\int_0^\infty\frac{t^n}{n!}e^{-e^t}dt$ accurately.

How can I obtain good asymptotics for $$\gamma_n=\displaystyle\int_0^\infty\frac{t^n}{n!}e^{-e^t}dt\text{ ? }$$ [This has been already done] In particular, I would like to obtain asymptotics that ...
4
votes
3answers
227 views

Asymptotic expansion of $J(t) = \int^{\infty}_{0}{\exp(-t(x + 4/(x+1)))}\, dx$

I want to derive an asymptotic expansion for the following Bessel function. I think I need to rewrite it in another form, from which I can integrate it by parts. I am interested in obtaining the ...
13
votes
6answers
749 views

A question on the Stirling approximation, and $\log(n!)$

In the analysis of an algorithm this statement has come up:$$\sum_{k = 1}^n\log(k) \in \Theta(n\log(n))$$ and I am having trouble justifying it. I wrote $$\sum_{k = 1}^n\log(k) = \log(n!), \ \ ...
2
votes
2answers
479 views

On the growth order of an entire function $\sum \frac{z^n}{(n!)^a}$

Here $a$ is a real positive number. The result is that $f(z)=\sum_{n=1}^{+\infty} \frac{z^n}{(n!)^a}$ has a growth order $1/a$ (i.e. $\exists A,B\in \mathbb{R}$ such that $|f(z)|\leq ...
10
votes
8answers
909 views

Limit of $\frac{\log(n!)}{n\log(n)}$ as $n\to\infty$.

I can't seem to find a good way to solve this. I tried using L'Hopitals, but the derivative of $\log(n!)$ is really ugly. I know that the answer is 1, but I do not know why the answer is one. Any ...
8
votes
1answer
246 views

How do I prove $\sum_{n \leq x} \frac{\mu (n)}{n} \log^2{\frac{x}{n}}=2\log{x}+O(1)$? Can I use Abel summation?

I am wondering if it is possible to solve this problem using Abel summation: $$\sum_{n \leq x} \frac{\mu (n)}{n} \log^2{\frac{x}{n}}=2\log{x}+O(1)$$ Or maybe I am on the wrong track?
7
votes
1answer
136 views

Speed of convergence of Riemann sums

This question is inspired by a previous question. It was shown that, for all function $f \in \mathcal{C} ([0, 1])$, $$ \lim_{n \to + \infty} \sum_{k=0}^{n} f \left( \frac{k}{n+1} \right) - ...
7
votes
3answers
277 views

Asymptotic for the integral involving exponential

The integrand seems extremely easy: $$I_n=\int_0^1\exp(x^n)dx$$ I want to determine the asymptotic behavior of $I_n$ as $n\to\infty$. It's not hard to show that $\lim_{n\to\infty}I_n=1$ follows from ...