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

learn more… | top users | synonyms (1)

30
votes
1answer
1k 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, ...
5
votes
4answers
3k 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 ...
17
votes
2answers
880 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}\left[\sum^n_{k=1}\frac{1}{k}-\ln(n)\right]=0.5772\ldots$$ No clue at all. Need help! Appreciated!
17
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.
14
votes
2answers
501 views

Asymptotic integral expansion of $\int_0^{\infty} t^{3/4}e^{-x(t^2+2t^4)}dt$ for $x \to \infty$

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: ...
17
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 = ...
10
votes
5answers
745 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)?$$
12
votes
3answers
982 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 ...
4
votes
4answers
549 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)$
36
votes
2answers
2k 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 ...
19
votes
2answers
658 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 ...
7
votes
1answer
318 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 ...
3
votes
2answers
175 views

Find the asymptotic tight bound for $T(n) = 4T(n/2) + n^{2}\log n$

Find the asymptotic tight bound in $$ T(n) = 4T\left(\frac{n}{2}\right) + n^{2}\log n. $$ where $ \log n= \log _{2}n $ and $T(1) = 1$. I should solve this using all three common methods: iteration, ...
10
votes
3answers
671 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 ...
9
votes
2answers
293 views

Known bounds for the number of groups of a given order.

The number of nonisomorphic groups of order $n$ is usually called $\nu(n)$. I found a very good survey about the values. $\nu(n)$ is completely known absolutely up to $n=2047$, and for many other ...
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 ...
21
votes
2answers
1k 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 ...
24
votes
2answers
1k 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?
4
votes
1answer
140 views

Divisor function asymptotics

Define $\tau_{r}(n) = \sum_{d_1...d_r = n}1$. One exercise in a book on sieve theory asked for an elementary proof by induction of the fact that $$\sum_{n\le x}\tau_r(n) = \frac{1}{(r - 1)!}x(\ln ...
8
votes
2answers
662 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
494 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)$?
8
votes
1answer
200 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) - ...
2
votes
1answer
328 views

Limit of the sequence $nx_{n}$ where $x_{n+1} = \log (1 +x_{n})$

Suppose $x_{1}>0$, and consider the sequence, $\{x_{n}\}$ defined as follows: $$x_{n+1}=\log(1+x_{n}) \quad n\geq 1 $$ Find the value of $\displaystyle \lim_{n \to \infty} nx_{n}$ I am having trouble ...
1
vote
2answers
161 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) $$
1
vote
2answers
262 views

Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
18
votes
6answers
1k views

Is there a slowest rate of divergence of a series?

$$f(n)=\sum_{i=1}^n\frac{1}{i}$$ diverges slower than $$g(n)=\sum_{i=1}^n\frac{1}{\sqrt{i}}$$ , by which I mean $\lim_{n\rightarrow \infty}(g(n)-f(n))=\infty$. Similarly, $\ln(n)$ diverges as fast as ...
21
votes
2answers
807 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
582 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
503 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
5k 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 ...
10
votes
4answers
425 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
2answers
2k 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 ...
23
votes
2answers
829 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
713 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.
8
votes
0answers
159 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 ...
1
vote
1answer
184 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
209 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
246 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
544 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 ...
3
votes
1answer
334 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 ...
3
votes
1answer
75 views

What is the proper way to handle the limit with little-$o$?

I was hoping to show that $$\left(1-\frac{x}{n}+o\left(\frac{2x}{n}\right)\right)^n \xrightarrow{n\to\infty} e^{-x}$$ which would be just fine without the little-$o$. Trying binomial formula: ...
3
votes
1answer
2k views

little-o and its properties

I know that $f(x) = o(g(x))$ for $x \to \infty $ if (and only if) $\lim_{x \to \infty}\frac{f(x)}{g(x)}=0$ Which means than $f(x)$ has a order of growth less than that of $g(x)$. 1) I'm still ...
3
votes
1answer
138 views

How to estimate the growth of a “savage” function near 1?

Say I have a function which exists within the unit disk, say $$f(x)=a_0+a_1x+a_2x^2+...$$ If we know sufficient information about the coefficients, say we know the growth rate of ...
1
vote
0answers
122 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
100 views

The order of convergence and the asymptotic error constant of the sequence $p_n=g(p_{n-1})$

Let $g(x)=0.5(x+a/x)$. Determine the order of convergence and the asymptotic error constant of the sequence $p_n=g(p_{n-1})$ toward $x=a^{.5}$. This is a problem in our homework in the class ...
0
votes
1answer
1k 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 ...
173
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!}}}}}) ...
31
votes
1answer
694 views

What's the most efficient way to mow a lawn?

For $S\subseteq\Bbb R^2$ and $x\in\Bbb R$, define $E_x(S)=\{y\in\Bbb R^2:d(y,S)<x\}$. ($E_x(S)$ represents the expansion of $S$ by $x$.) Given a path $\gamma:[0,1]\to\Bbb R^2$, denote its length as ...
24
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 ...