Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.
156
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!}}}}}) ...
29
votes
0answers
632 views
On the number of complete and gap-free compositions
This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
27
votes
3answers
522 views
Sequence of numbers with prime factorization $pq^2$
I've been considering the sequence of natural numbers with prime factorization $pq^2$, $p\neq q$; it begins 12, 18, 20, 28, 44, 45, ... and is A054753 in OEIS. I have two questions:
What is the ...
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 ...
25
votes
3answers
491 views
Expected length of the shortest polygonal path connecting random points
$N$ points are selected in a uniformly distributed random way in a disk of a unit radius. Let $L(N)$ denote the expected length of the shortest polygonal path that visits each of the points at least ...
25
votes
1answer
847 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 ...
25
votes
1answer
741 views
How many primes does Euclid's proof account for?
This is a passing curiosity, and I haven't found any duplicates, so I thought I'd share my thoughts.
In the most basic (or at least the most famous) proof of the infinitude of prime numbers, due to ...
24
votes
1answer
455 views
Power towers: to infinity and all the way back
In the following, let $n$ be a positive integer, all other variables be real (furthermore, $a>1$), all functions be real-valued, and logarithms of negative arguments be undefined.
Let
...
23
votes
2answers
761 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 ...
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 ...
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 ...
20
votes
5answers
686 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.
20
votes
2answers
740 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 ...
20
votes
3answers
481 views
Asymptotic expression of an oscillatory integral
Consider the integral
$$ f(\alpha,\beta)= \int_0^{2\pi}\,dx \sqrt{1- \cos(\alpha x ) \cos(\beta x)}$$ as a function of the two parameters $\alpha,\beta$. I am interested in the asymptotic behavior ...
19
votes
2answers
981 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?
19
votes
7answers
1k views
Is there a formula for $\sum_{n=1}^{k} \frac1{n^3}$?
I am searching for the value of $$\sum_{n=k+1}^{\infty} \frac1{n^3} \stackrel{?}{=} \sum_{n = 1}^{\infty} \frac1{n^3} - \sum_{n=1}^{k} \frac1{n^3} = \zeta(3) - \sum_{n=1}^{k} \frac1{n^3}$$
For which ...
18
votes
2answers
482 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 ...
18
votes
2answers
415 views
Asymptotic analysis of the integral $\int_0^1 \exp\{n (t+\log t) + \sqrt{n} wt\}\,dt$
The integral I'm trying to study is
$$
F(n) = \int_0^1 \exp\left\{n(t+\log t)+\sqrt{n}wt\right\}\,dt,
\tag{1}
$$
where $w$ is a fixed complex number with $\Re(w) < 0$ and $\Im(w) > 0$. As ...
17
votes
2answers
711 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 ...
15
votes
3answers
987 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.
15
votes
4answers
596 views
Decreasing integers on the blackboard
There are $n\geq 2$ copies of an integer $k>0$ written on the blackboard. A move consists of choosing an integer $m>0$ on the blackboard, and replacing it as well as one other integer on the ...
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 = ...
14
votes
2answers
345 views
What's the lower bound of the sum $S(n) = \sum_{k=1}^n \prod_{j=1}^k(1-\frac j n)$?
If we have
$$
S(n) = \sum_{k=1}^n \prod_{j=1}^k(1-\frac j n)
$$
What the lower bound of $S(n)$ when $n\to\infty$?
PS: If I didn't make any mistake when I calculate $S(n)$, then it should be ...
14
votes
3answers
421 views
Can a function “grow too fast” to be real analytic?
Does there exist a continuous function $\: f : \mathbf{R} \to \mathbf{R} \:$ such that for
all real analytic functions $\: g : \mathbf{R} \to \mathbf{R} \:$, for all real numbers $x$,
there exists ...
14
votes
3answers
214 views
Sufficient bound to conclude limit has certain value. $\lim {\left( {\int_0^1 {{{dx} \over {1 + {x^n}}}} } \right)^n}=\frac 1 2 $
I am trying to show that
$$\lim {\left( {\int\limits_0^1 {{{dx} \over {1 + {x^n}}}} } \right)^n}=\frac 1 2 $$
Now, this can be done as follows. Using $x\mapsto x^{-1}$ we get that
$$\int\limits_0^1 ...
14
votes
2answers
526 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
5answers
866 views
Is there any nonconstant function that grows (at infinity) slower than all iterations of the (natural) logarithm?
Is there any nonconstant function that grows (at $\infty$) slower than all iterations of the (natural) logarithm?
Thanks for your help.
13
votes
4answers
432 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 ...
13
votes
6answers
740 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!), \ \ ...
13
votes
3answers
436 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$?
13
votes
4answers
353 views
Asymptotic formula for $\sum_{n \le x} \frac{\varphi(n)}{n^2}$
Here is yet another problem I can't seem to do by myself... I am supposed to prove that
$$\sum_{n \le x} \frac{\varphi(n)}{n^2}=\frac{\log x}{\zeta(2)}+\frac{\gamma}{\zeta(2)}-A+O \left(\frac{\log ...
13
votes
2answers
352 views
On the Limit of Stirling's Approximation
I have recently proven the following curious identity: For real $x \geqslant 1$,
\begin{align}
\lfloor x \rfloor! = x^{\lfloor x \rfloor} e^{1-x} e^{\int_{1}^{x} \text{frac}(t)/t \ dt}
\end{align}
...
13
votes
1answer
191 views
If $\lambda_n \sim \mu_n$, is it true that $\sum \exp(-\lambda_n x) \sim \sum \exp(-\mu_n x)$ as $x \to 0$?
If $\lambda_n,\mu_n \in \mathbb{R}$, $\lambda_n \sim \mu_n$ as $n \to +\infty$, and $\mu_n \to +\infty$ as $n \to +\infty$, is it true that
$$
\sum_{n=1}^{\infty} \exp(-\lambda_n x) \sim ...
12
votes
5answers
555 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 ...
12
votes
3answers
403 views
A recurrence that wiggles?
Consider the following sequence $a_n$:
$a_1 = 0$
$a_n = 1 + \frac{1}{2^n-2} \sum_{i=1}^{n-1} \binom{n}{i} a_i$
The first few terms are $0,1,\frac{3}{2},\frac{13}{7},\frac{15}{7}$.
The sequence ...
12
votes
3answers
811 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 ...
12
votes
2answers
333 views
Asymptotics of the sum of squares of binomial coefficients
We are trying to estimate the cardinality $K(n,p)$ of so-called Kuratowski monoid with $p$ positive and $n$ negative linearly ordered idempotent generators. In particular, we are interesting in the ...
12
votes
1answer
281 views
Estimating the integral $\int_0^1 (1-t^2)^{-1/2} e^{-nt} \,dt$ for large $n$.
I would like to find the asymptotic behavior of the integral
$$\int_0^1 (1-t^2)^{-1/2} e^{-nt} \,dt$$
for large $n$. It seems reasonably obvious that the integral goes to zero. At least it is ...
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, ...
11
votes
6answers
387 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, ...
11
votes
2answers
342 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:
...
11
votes
2answers
411 views
Asymptotics of LCM
Let $\operatorname{LCM}(x_1,x_2,\ldots,x_n)$ be the least common multiple of the integers $x_i$.
How can one find the asymptotics of $\operatorname{LCM}(f(1),f(2),\dots,f(n))$ as $n$ approaches ...
11
votes
1answer
182 views
Calculate Asymptotics of Integral?
Let $f$ be a continuous function on $[0,1]$. How do I calculate the asymptotics, as $n\rightarrow\infty$, of
$\displaystyle \int_{[0,1]^n}f\left(\frac{x_1+...+x_n}{n}\right)\text d x_1...\text d ...
11
votes
3answers
363 views
The boundedness of an integral
Is there a constant $C$ which is independent of real numbers $a,b,N$, such that
$$\left| {\int_{-N}^N \dfrac{e^{i(ax^2+bx)}-1}{x}dx} \right| \le C?$$
11
votes
3answers
284 views
Closed form for $\sum_{k=0}^{n} k\binom{n}{k}\log\binom{n}{k}$
Is it possible to write this in closed form:
$$\sum_{k=0}^{n} k\binom{n}{k}\log\binom{n}{k}$$
Can you get something like $$n2^{n-1}\log(2^{n-1})$$
11
votes
1answer
92 views
Expected values of some properties of the convex hull of a random set of points
$N$ points are selected in a uniformly distributed random way in a disk of the unit radius. Let $P(N)$ and $A(N)$ denote the expected perimeter and the expected area of their convex hull.
For what ...
10
votes
5answers
590 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)?$$
10
votes
8answers
894 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 ...
10
votes
2answers
1k views
Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?
I want an upper bound on $$\sum_{i=1}^k \binom{n}{i}.$$
$O(n^k)$ seems to be an overkill -- could you suggest a tighter bound ?
10
votes
2answers
425 views
How prove this sequence $a_{n}=\sqrt{n}+\frac{1}{2}-\frac{1}{8\sqrt{n}}+o\left(\frac{1}{\sqrt{n}}\right)?$
let sequence $\{a_{n}\}$ such $$a_{1}=1,a_{n+1}=1+\dfrac{n}{a_{n}}$$
show that:
$$a_{n}=\sqrt{n}+\dfrac{1}{2}-\dfrac{1}{8\sqrt{n}}+o\left(\dfrac{1}{\sqrt{n}}\right)?$$
This result is china student ...
