Hot answers tagged asymptotics
10
The equality is true. Recall that $\mathcal{O}(n)$ means the function is eventually $\leq C n$, where $C$ is a positive constant.
In your case, show that $n^{1/n} < e^{1/e}$ by considering the function $x^{1/x}$. We hence have for all $n \in \mathbb{N}$, $$n \cdot n^{1/n} < e^{1/e} \cdot n$$ Since, we have $n \cdot n^{1/n} < ...
9
You can expand the exponential in a Taylor series quite accurately:
$$\exp{\left ( x^n \right )} = 1 + x^n + \frac12 x^{2 n} + \ldots$$
Because $x \in [0,1]$, this series converges rapidly as $n \to \infty$.
Then the integral is
$$1 + \frac{1}{n+1} + \frac12 \frac{1}{2 n+1} + \ldots = \sum_{k=0}^{\infty}\frac{1}{k!} \frac{1}{k n+1}$$
We can rewrite this ...
8
Naive Approach:
$$
\begin{align}
\int_{-\infty}^\infty f(x)\,e^{-Ax^2}\,\mathrm{d}x
&=\sum_{k=-\infty}^\infty\int_0^1f(x)\,e^{-A(x+k)^2}\,\mathrm{d}x\\
&=\int_0^1f(x)\sum_{k=-\infty}^\infty e^{-A(x+k)^2}\,\mathrm{d}x\tag{1}
\end{align}
$$
For $x\in[0,1]$ and $k\ge0$,
$$
e^{-A(x+k+1)^2}
\le\int_{x+k}^{x+k+1} e^{-At^2}\,\mathrm{d}t
\le ...
8
The numerator is
$$ \log(n!) = \log 1 + \log 2 + \log 3 + \cdots + \log n $$
The terms have an obvious upper bound: $\log n$. Thus,
$$ \log(n!) \leq \log n + \log n + \log n + \cdots + \log n = n \log n $$
Thus, $\log(n!) / (n \log n) \leq 1$, always.
Half of the terms have an obvious lower bound: $\log (n/2)$.
$$ \log(n!) \geq (n/2) \log(n/2) $$
...
6
First, use that $n^n > n!$ for all $n > 1$, thus $n \log(n) > \log(n!)$ and so $1 > \dfrac{\log(n!)}{n \log(n)}$. Now, from a basic theorem of Stirling's approximation, we have $n \log(n) - n < \log(n!)$, so we have $1 - \dfrac{1}{\log(n)} < \dfrac{\log(n!)}{n \log(n)}$. Combining these, we have $1 - \dfrac{1}{\log(n)} < ...
5
Let $n \geq 1$. A first crude estimate can be obtained as follows. Substitute $x \leftarrow x^{1/n}$ to get
$$ I_n = \frac{1}{n}\int_0^1 x^{\frac{1}{n} - 1} e^x dx.
$$
Now we can estimate $e^x$ on the interval $[0,1]$ to get
$$
\frac{1}{n}\int_0^1 x^{\frac{1}{n}-1}(1+x)\, dx < I_n < \frac{1}{n}\int_0^1 x^{\frac{1}{n} - 1} (1 + (e-1)x)\, dx
$$
or
$$
...
5
If $O(n^2)-O(n^2)$ is defined as the set of sequences $(z_n)$ such that there exists $(x_n)$ and $(y_n)$ with $x_n\in O(n^2)$, $y_n\in O(n^2)$, and, for all $k$, $z_k=x_k-y_k$, then $O(n^2)-O(n^2)=O(n^2)$, as readily seen by proving the double inclusion.
More generally, for every sequences $(x_n)$ and $(y_n)$, $O(x_n)-O(y_n)=O(z_n)$ with $z_n=|x_n|+|y_n|$ ...
4
Note that $$f(n^2)=\lceil\lg\lg( n^2)\rceil!=\lceil\lg(2\lg n)\rceil!=\lceil1+\lg\lg n\rceil!=(1+\lg\lg n)\cdot f(n),$$
that is $\frac{f(n^2)}{f(n)}$ grows slower than $n$. On the other hand, with $g(n) = c n^a$, we have $\frac{g(n^2)}{g(n)}=n^a$, so this suggests that $a=1$ should suffice (or in fact any $a>0$). (To make this stringent, note that $f$ is ...
4
I will also do it formally though maybe with a less number of steps to justify. It is clear that since $f$ is periodic,
\begin{align}
\int_{-\infty}^{\infty}f(x)e^{-Ax^2}dx&=\int_0^1 f(x)\sum_{n\in\mathbb{Z}}e^{-A(x+n)^2}dx=\\&=
\int_0^1 f(x)e^{-A x^2}\vartheta_3\Bigl(iAx\Bigl|\Bigr.\frac{iA}{\pi}\Bigr)dx,\tag{1}
\end{align}
where ...
4
One way to look at this is as follows. Let $c = \int_0^1 f(x)\,dx$. Then $f(x) - c$ has integral $0$ over the period, and therefore is the derivative of a $C^1$ function $g(x)$ on ${\mathbb R}$ which also has period $1$. Then
$$\int_{-\infty}^{\infty} f(x) e^{-Ax^2}\,dx = \int_{-\infty}^{\infty} c e^{-Ax^2}\,dx +
\int_{-\infty}^{\infty} (f(x) - c) ...
4
Theorem. $\lim_{n\to\infty} K(n,n)/\binom {2n}n^2=16/9$.
This theorem is a corollary of the following results.
For every integers $0\le a,b\le n$ put $c_{a,b}(n)=\binom {2n-a-b}{n-a}/\binom {2n}n$.
Lemma 1. For every integers $a,b\ge 0$ there exists a limit $\lim_{n\to\infty} c_{a,b}(n)=2^{-(a+b)}$.
Proof. It follows from the equality $c_{a,b}(n)=\frac ...
4
We write the integrand as
$$
\begin{align}
\frac{1}{1+n\pi\sin x + x\sin x} &= \frac{1}{1+n\pi\sin x} \cdot \frac{1}{1+\frac{x\sin x}{1+n\pi\sin x}} \\
&=\frac{1}{1+n\pi\sin x} \left[1 + O\left(\frac{x\sin x}{1+n\pi\sin x}\right)\right],
\end{align}
$$
where the $O(\cdots)$ holds uniformly for $n\geq 1$ and $x \in [0,\pi/2]$, so that
$$
...
3
Hint: Let $x=r\cos\theta$, $y=\frac{1}{2}r\sin\theta$ and note that
$$f(x,y)=f(0,0)+x\frac{\partial f}{\partial x}(0,0)+y\frac{\partial f}{\partial y}(0,0)+\frac{1}{2}\left(x^2\frac{\partial^2 f}{\partial x^2}(0,0)+2xy\frac{\partial^2 f}{\partial x\partial y}(0,0)+y^2\frac{\partial^2 f}{\partial y^2}(0,0)\right)+O(r^3).$$
3
At least one direction fails. Take the function $f(x)=x$, and modify it by adding a bump function that, for every positive integer $n$, is $0$ between $n$ and $n+e^{-n}$, climbs to $1$ at $n+e^{-2n}$, and falls back to $0$ at $n+e^{-3n}$. All derivatives exist, but the first derivative is very wild for large $x$.
2
No, Big-Theta control over a function does not imply control over its derivatives. Imagine that $g(x)$ is "oscillating around" the function $f(x)$.
Here's an example.
Suppose that $f(x)$ is the constant function $f(x) \equiv 10$, say.
If $g(x)= \sin e^x$, then it is a bounded function, taking values in $[0,2]$. However, its derivative $g'(x) = e^x \cos ...
2
You have :
$$ M^{1/k} = 1 + \frac{1}{k} \ln M + \frac{1}{2} \ln^2 M \frac{1}{k^2} + O(1/k^3)$$
Since
$$\sum_{k=1}^n \frac{1}{k} = \ln n + \gamma + \frac{1}{2n} + O(1/n^2)$$
$$\sum_{k=1}^n \frac{1}{k^2} = \frac{\pi^2}{6} - \frac{1}{n} + O(1/n^2)$$
we deduce :
$$\sum_{k=1}^n M^{1/k} = n + \ln M. \ln n + C + (\ln M + \ln^2 M) \frac{1}{2n} + O(1/n^2),$$
for some ...
2
The symbol $o(|h|)$ is like a variable for a function $g(h)$ that satisfies $$\lim_{h \rightarrow 0} \frac{g(h)}{|h|} = 0.$$ Multiplying any such function by a constant gives you another function in that class, so we write $co(|h|) = o(|h|).$ Similarly, adding any two functions in that class gives another function in that class, so $o(|h|) + o(|h|) = ...
2
The argument you've written down shows that
$$K(n, n) \le \sum_{k=0}^{2n} {2k \choose k}.$$
Stirling's formula gives the asymptotic
$${2k \choose k} \sim \frac{4^k}{\sqrt{\pi k}}$$
so this sum behaves approximately like a geometric series, and we expect that
$$\sum_{k=0}^{2n} {2k \choose k} \sim \frac{4}{3} \left( \frac{4^{2n}}{ \sqrt{2 \pi n} } ...
2
The formally correct $O$-notation has been explained in http://www.artofproblemsolving.com/Forum/viewtopic.php?f=296&t=31517&start=20 . Namely, suppose we have been given a positive $g$ defined in a punctured neighborhood of $x_0$. Now $O_{x_0}(g)$ is the class of all functions $f$ such that the ratio $f/g$ is bounded in some punctured neighbourhood ...
2
A related technique. Here is a start. Integrating by parts gives,
$$I= {{\rm e}}-{\frac {{{\rm e}}\,n}{1+n}}+{\frac {{{\rm e}}\,{n}^{
2}}{2\,{n}^{2}+3\,n+1}}-{\frac {{{\rm e}}\,{n}^{3}}{6\,{n}^{3}+11\,{
n}^{2}+6\,n+1}}$$
$$+{\frac{{{\rm e}}\,{n}^{4}}{24\,{n}^{4}+50\,{n}^{3}+
35\,{n}^{2}+10\,n+1}}-\int _{0}^{1}\!{\frac {{n}^{5}{{\rm e}^{{
...
2
From the Taylor series of $e^x$, we have
$$e^x = 1 + \sum_{k=1}^{\infty} \dfrac{x^n}{n!}$$
From this we get that, $e^x \geq \dfrac{x^n}{n!}$, for $x \in \mathbb{R}^+$ and $n \in \mathbb{Z}^+$.
Setting $x=n$ we get that
$$e^n \geq \dfrac{n^n}{n!} \implies n! \geq \left(\dfrac{n}e \right)^n$$
Hence, we have
$$\log(n!) \geq n \log n - n$$
Also, note that ...
2
All you need show to prove $f(n) = O(g(n))$ is that for some $N$ and some $C$ that
$$
|f(n)| < c|g(n)|\quad\text{for all}\quad n\ge N.
$$
You need not be at all efficient about this. So, to show $5n^3+7n+1 = O(n^3)$, assume $n \ge N = 1$.
$$
\begin{aligned}
5n^3+7n+1 &\le5n^3+7n^3 + 1\cdot n^3\\
&= 13n^3
\end{aligned}
$$
You can reduce the ...
2
No. Not the way You described it. The functional equation
$$
\pi ^{-s/2} \Gamma \left( \frac{s}{2} \right) \zeta \left( s \right) = \pi ^{-(1-s)/2} \Gamma \left( \frac{1-s}{2} \right) \zeta \left( 1-s \right)
$$
links region to the right of the critical line to the region to the left of the critical line. More precisely, it links behavior of zeta at $s$ ...
2
For nonnegative sequences $(f(n))$ and $(g(n))$, writing $f(n)=O(g(n))$ means there exists a real constant $c>0$ and $n_0\in\Bbb N$ such that for all $n\geq n_0$, $f(n)\leq c g(n)$, and that's all !
In your case, since $\displaystyle\lim_{n\to+\infty} \dfrac{n^k}{2^n}=0$, you know that $0<\dfrac{n^k}{2^n}\leq 1$ for $n$ sufficiently large, for ...
2
$\lceil{\log n}\rceil! \geq (\log n)! \approx \bigg(\frac{\log n}{e} \bigg)^{\log n} \sqrt{2 \pi \log n}$
At the same time a polynomial function is $n^a, \ a \in \mathbb{Z^+}$, hence
$$
n^a = e^{\log n^a} = (e^a)^{\log n}
$$
where $e^a$ is a constant. Obviously $\frac{\log n}{e} \geq e^a \ n \ \forall \geq e^{e^{a+1}}$
Hence $\lceil{\log n}\rceil!$ ...
2
Hint: It's an indeterminate form $\frac{\infty}{\infty}$, and you can attempt L'Hopital's rule. One application changes the situation a little: it is the same indeterminate form, but instead of $n^k$ you have $kn^{k-1}$. Don't forget you can apply L'Hopital's rule to this new expression (and several times more, if necessary!)
2
Note that $\frac{2^n}{n!}=\frac{2\times 2 \times 2\cdots \times 2}{1\times 2 \times 3\times 4\cdots \times n} \le 2$ for all $n$. Hence $|2^n| \le 2 |n!|$ for all $n$.
Suppose that there is an $M$ such that $|n!| \le M |2^n|$ for all $n$ (sufficiently large). Try to find a contradiction.
1
You know that $|X_n-c|>\epsilon$ has probability converging to 0. You want the same for $|g(X_n)-g(c)|>\delta$.
Suppose you take $b<c<d$. Choose them so that $|g(x)-g(c)|<\delta$ for $b<x<d$. Now evaluate the probability that $X_n$ is not in this range.
In response to your solution: You're right about the point which is shaky. The ...
1
$$(1)\;\;\text{Look at the positive series}\;\sum_{n=1}^\infty\frac{2^n}{n!}$$
$$(2)\;\;\frac{a_{n+1}}{a_n}=\frac{2^{n+1}}{(n+1)!}\cdot\frac{n!}{2^n}=\frac2{n+1}\xrightarrow[n\to\infty]{}0 \;,\;\text{thus} $$
$$(3)\;\;\text{The series in (1) converges}$$
$$(4)\;\;a_n=\frac{2^n}{n!}\xrightarrow[n\to\infty]{}0$$
Thus, for some
$$N\in\Bbb ...
1
You are interested in the asymptotic behaviour; you can show that any $T$ satisfying the second relation is monotone (increasing), and then you can use the "sandwiching" theorem to relate solutions to the second to solutions to the first —up to some term which will, in hindsight (once you have the solution to the first relation) prove to be negligible.
Only top voted, non community-wiki answers of a minimum length are eligible
