Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.
143
votes
1answer
6k 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!}}}}}) ...
25
votes
3answers
371 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 ...
23
votes
1answer
546 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 ...
22
votes
2answers
654 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 ...
22
votes
1answer
673 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 ...
20
votes
9answers
2k 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 ...
20
votes
2answers
829 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
621 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 ...
19
votes
3answers
390 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 ...
18
votes
5answers
619 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.
18
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 ...
17
votes
6answers
937 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 ...
16
votes
2answers
705 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?
15
votes
2answers
351 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 ...
15
votes
2answers
265 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 ...
14
votes
2answers
470 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
3answers
676 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.
13
votes
6answers
2k 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 = ...
13
votes
2answers
327 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
2answers
305 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 ...
12
votes
3answers
367 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
2answers
309 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 ...
12
votes
6answers
564 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!), \ \ ...
12
votes
3answers
471 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
4answers
341 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 ...
12
votes
3answers
249 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 ...
12
votes
3answers
165 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 ...
12
votes
1answer
202 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
3answers
217 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
2answers
361 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 ...
11
votes
1answer
146 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 ...
11
votes
3answers
249 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})$$
10
votes
5answers
467 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
233 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
636 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
299 views
Positive integers $k = p_{1}^{r_{1}} \cdots p_{n}^{r_{n}} > 1$ satisfying $\sum_{i = 1}^{n} p_{i}^{-r_{i}} < 1$
A divisor $d$ of $k = p_{1}^{r_{1}} \cdots p_{n}^{r_{n}}$ is unitary if and only if $d = p_{1}^{\varepsilon_{1}} \cdots p_{n}^{\varepsilon_{n}}$, where each exponent $\varepsilon_{i}$ is either $0$ or ...
10
votes
2answers
364 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 ...
10
votes
1answer
268 views
Asymptotic estimate for Riemann-Lebesgue Lemma
Let $f$ be a real-valued, $L^1$ integrable function on the interval $[a,b]$. Then the Riemann-Lebesgue Lemma tells us that: $$\int_a^bf(x)\sin(2\pi nx)dx\rightarrow0 \text{ as } ...
10
votes
2answers
186 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:
...
10
votes
2answers
178 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 ...
10
votes
1answer
139 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 ...
9
votes
5answers
346 views
Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $.
Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $, with induction.
I get the intuition behind this question. Clearly, the given function isn’t even growing ...
9
votes
4answers
277 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
3answers
290 views
Approximation of elements in arithmetic progressions by logarithms of integers
For fixed $a,b,c \in \mathbb{R}$ with $ac \neq 0$, it seems to me that one can find an increasing sequence of integers $\{\alpha_n\}$ such that the quantity $c \log \alpha_n$ becomes arbitrarily close ...
9
votes
0answers
224 views
Asymptotic related to the infinite product of sine
The amount is somewhat complicated ($x$ is a constant):
$$S_n=\sum_{k=1}^n\ln\left(1-\frac{\sin^2\big(x/(2n+1)\big)}{\sin^2\big(k\pi/(2n+1)\big)}\right)\tag{*}$$
I want to enrich my handy powerful ...
8
votes
1answer
226 views
What is $Θ(f(n)) - Θ(f(n))$?
$$\Theta(f(n)) - \Theta(f(n)) =\; ?$$
I find this exercise from my algorithm analysis book very confusing because it's subtracting 2 function sets. Any hints/answers are welcome.
Thanks!
8
votes
2answers
339 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 ...
8
votes
1answer
765 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, ...
8
votes
1answer
138 views
Mean Value of a Multiplicative Function close to $n$ in Terms of the Zeta Function.
Let $f(n)$ be a multiplicative function defined by $f(p^a)=p^{a-1}(p+1)$, where $p$ is a prime number. How could I obtain a formula for $$\sum_{n\leq x} f(n)$$ with error term $O(x\log{x})$ and ...
8
votes
1answer
227 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?
