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

learn more… | top users | synonyms (1)

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

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

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 ...
31
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 ...
30
votes
1answer
558 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
964 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
575 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 ...
25
votes
3answers
543 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
476 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
471 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
810 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
796 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
4k 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
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
3answers
516 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
703 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
770 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
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
892 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
576 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
445 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
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
492 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
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.
16
votes
4answers
626 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
305 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)$? ...
14
votes
2answers
719 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
357 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
450 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
359 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
568 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
231 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
5answers
955 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 ...
13
votes
6answers
825 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
470 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
490 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
163 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
4answers
376 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
194 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
126 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
3answers
456 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
919 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
391 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
2answers
384 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: ...
12
votes
1answer
337 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
1answer
303 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 ...
12
votes
1answer
261 views

Upper bound for the widest matrix with no two subsets of columns with the same vector sum

Over at PPCG there is an ongoing contest going on to find the largest matrix without a certain property, called property $X$. The description is as follows (copied from the question). A circulant ...
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, ...