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

learn more… | top users | synonyms (1)

170
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!}}}}}) ...
56
votes
1answer
1k views

Why are asymptotically one half of the integer compositions gap-free?

Question summary The number of gap-free compositions of $n$ can already for quite small $n$ be very well approximated by the total number of compositions of $n$ divided by $2$. This question seeks ...
33
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 ...
32
votes
1answer
614 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 ...
29
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 ...
28
votes
3answers
606 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
3answers
570 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 ...
26
votes
1answer
504 views

Zombie outbreak on a $k$-regular graph

Suppose we have a zombie outbreak on a connected $k$-regular graph of order $n$. There are $n_0$ initially infected zombie nodes, and each turn, each zombie infects its neighbors with probability ...
25
votes
1answer
486 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 ...
25
votes
1answer
835 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 ...
23
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 ...
23
votes
2answers
808 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
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?
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 ...
21
votes
2answers
794 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 ...
21
votes
3answers
533 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 ...
20
votes
5answers
709 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
618 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 ...
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 ...
19
votes
2answers
976 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 ...
18
votes
2answers
466 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
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.
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 = ...
17
votes
1answer
507 views

Double harmonic summation

Let us consider a lattice formed by all points with integer and positive coordinates on a Cartesian plane, and where $K$ is the maximal value for the $x$-axis. Let us assign to each lattice point the ...
16
votes
4answers
633 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 ...
16
votes
2answers
316 views

$f=\underset{+\infty}{\mathcal{O}}\bigr(f''\bigl)$ implies that $f=\underset{+\infty}{\mathcal{O}}\bigr(f'\bigl)$.

Let $f\in\mathcal{C}^2(\Bbb{R},\Bbb{R})$ be a positive function such that $f=\underset{+\infty}{\mathcal{O}}\bigr(f''\bigl)$ does it implies that $f=\underset{+\infty}{\mathcal{O}}\bigr(f'\bigl)$? ...
15
votes
5answers
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 ...
14
votes
2answers
796 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!
14
votes
2answers
360 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
473 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
2answers
366 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} ...
14
votes
2answers
575 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 ...
14
votes
3answers
232 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
1answer
207 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 ...
13
votes
5answers
1k 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 infinity slower than all iterations of the (natural) logarithm?
13
votes
3answers
466 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 ...
13
votes
6answers
860 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
4answers
490 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
3answers
496 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
3answers
170 views

An equivalent for $\sum_{n=0}^{\infty} e^{-x\sqrt{n}}$ as $x$ tends to $0^+$

I would like to obtain an equivalent form for $$ f(x)=\sum_{n=0}^{\infty} e^{-x\sqrt{n}} $$ as $x \rightarrow 0^+$. I tried without success to "remove" the $\sqrt{\cdot}$ in the summand by summing ...
13
votes
2answers
438 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: ...
13
votes
4answers
388 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
229 views

Convergence of power towers

Let's define the sequence $\{s_n\}$ recursively as $$s_1=\sqrt2,\ \ \ s_{n+1}=\sqrt2^{\,s_n}.$$ Or, in other words, $$s_n=\underbrace{\sqrt2^{\sqrt2^{\ .^{\ .^{\ .^{\sqrt2}}}}}}_{n\ \text{levels}}.$$ ...
13
votes
1answer
140 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 ...
12
votes
6answers
431 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, ...
12
votes
3answers
966 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
420 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
4answers
233 views

Infinite Sum of Sines With Increasing Period

A while ago, I was thinking about the Weierstrass function, which is a sum of sines with increasing frequencies in such a way that the curve is a fractal. However, I wondered what would happen if one ...
12
votes
1answer
345 views

Packing an infinite sequence of disks

Let $a > 1$ and $Q(a)$ denote the supremum of values of $q$ such that a countably infinite collection of disks, whose areas form an infinitely decreasing geometric progression with the start value ...
12
votes
2answers
245 views

When is this sum of perfect powers bounded

For any positive integers $n,d$, let $$ A_d(n)=\frac{\sum_{k=1}^n k^{2d}}{n(n+1)(2n+1)} $$ It is easy to see (and well-known) that for fixed $d$, $A_d(.)$ is a polynomial of degree $2d-2$. Writing ...