Tag Info

Hot answers tagged

6

Please consider: If $X_1,\ldots,X_n$ are identically and independently distributed, then by the strong law of large numbers: $\delta_1 \rightarrow kE|X|$ with $E|X|={\sigma}\sqrt{2/\pi}.$ So $\delta_1$ will converge to $\sigma$ iff $ k = \sqrt{\pi/2}$. Now we'll need $Var(|X|)=E(X^2)-E^2(|X|)=\sigma^2(1-2/\pi).$ The variance of $\delta_1 $ can be ...


4

The so-called master theorem is not needed anyway, neither here nor in many other questions of the same ilk asked on math.se so the fact that you require a solution not using it is quite welcome... Here we go: Just as when studying ordinary differential equations, we start with the linear part of the relation, that is, ...


4

This is correct: $$ \sqrt{a^2+4}=a\sqrt{1+\frac{4}{a^2}}=a+a\left(\sqrt{1+\frac{4}{a^2}}-1\right)=a+a\frac{1+\frac{4}{a^2}-1}{\sqrt{1+\frac{4}{a^2}}+1}\\=a+\frac{4}{a}\cdot\frac{1}{\sqrt{1+\frac{4}{a^2}}+1}\approx a+\frac{2}{a} $$


4

Congratulations! You have just won the lottery! You will receive cash every week for the rest of your life, on one of two schedules: \$1,000 today, \$1,002 next week, \$1,004 the week after that, and so on, \$1006, \$1008, \$1010… OR \$0.05 today, \$0.10 next week, \$0.20 the week after that, and so on, \$0.40, \$0.80, \$1.60… The first one gets you ...


4

These are my thoughts on the problem. They do not answer any of the three questions, but do not fit on a comment. Let $S_N$ be the $N$-th partial sum of the series and $L_n$ the lowest common multiple of $\{1,\dots,n\}$. Then $S_N$ is periodic of period $2\,L_n^2\,\pi$. $L_n$ is known to be of the order $e^{n(1+o(1))}$, so that the period is very large. ...


3

$$\sqrt{a^2+4}\sim a+\frac{1}{a}$$ as $a\to\infty$ if $$\lim_{a\to\infty}\frac{\sqrt{a^2+4}}{a+\frac{1}{a}}=1$$ But $$\lim_{a\to\infty}\frac{\sqrt{a^2+4}}{a+\frac{1}{a}}=\lim_{a\to\infty}\frac{a\sqrt{a^2+4}}{a^2+1}=\lim_{a\to\infty}\frac{a^2\sqrt{1+4/a^2}}{a^2(1+1/a^2)}=1$$


3

More precisely, $\sqrt{a^2+4} = a + 2/a + O(1/a^3)$ as $a \to \infty$. In fact it is easy to see that $$(a+2/a)^2 > a^2 + 4 > (a+2/a - 2/a^3)^2 \ \text{for} \ a > 1$$ so $$a + \dfrac{2}{a} > \sqrt{a^2 + 4} > a + \dfrac{2}{a} - \dfrac{2}{a^3}$$


3

If $n=2^k$, then the recurrence $$T(n)=4T(n/2)+n,$$ becomes $$ T\big(2^{k}\big)=4T\big(2^{k-1}\big)+2^k, $$ and hence, if we set $S(k)=T\big(2^k\big)$, then $S(k)$ satisfies the recurrence relation $$ S(k)=4S(k-1)+2^k, $$ and therefore $$ \frac{S(k)}{4^k}=\frac{S(k-1)}{4^{k-1}}+2^{-k}. $$ Thus $$ ...


2

Taking the reciprocal of Stirling's Asymptotic expansion as derived in this answer: $$ n!=\frac{n^n}{e^n}\sqrt{2\pi n}\left(1+\frac{1}{12n}+\frac{1}{288n^2}-\frac{139}{51840n^3}+O\left(\frac{1}{n^4}\right)\right) $$ we get $$ \frac1{n!}=\frac{e^n}{n^n}\frac1{\sqrt{2\pi ...


2

The notation $o(1)$ refers to any unspecified term going to $0$ hence you are asked to show that every $$(1+a(x))\cosh x-(1+b(x))\sinh(x)),$$ such that $a(x)\to0$ and $b(x)\to0$ can be written as $$(1+c(x))\mathrm e^{-x},$$ for some $c(x)\to0$. Since $\cosh x-\sinh x=\mathrm e^{-x}$, this is asking whether $$a(x)\cosh x-b(x)\sinh(x)=c(x)\mathrm e^{-x},$$ for ...


2

Looks right to me. I'd make it obvious that $x^2$ is the highest order term: turn it into polynomial-plus-remainder form (which may have a real name), using long or synthetic division. This gives $$\frac{3x^3+2x+1}{x+2}=3x^2-6x+14-\frac{27}{x+2}$$ Which makes life a lot easier: $3x^2$ obviously dominates for large $x$. Pick some $C$ values above and ...


2

No, asymptotic equivalence doesn't justify the limit $\lim_{x \to 0}\frac{\sin x}{x} = 1$. The limit justifies the equivalence.


2

That kind of asymptotics follows from the Central Limit Theorem. If we consider the binomial random variable $X=B(n,1/2)$ as the sum of $n$ independent Bernoulli trials, we have: $$\mathbb{E}[X]=\frac{n}{4}, \qquad \operatorname{Var}[X]=\frac{n}{4}$$ from which the approximation: $$\frac{1}{2^n}\binom{n}{n/2+r}\approx ...


2

Summing the inequalities $$\frac1{k^2}-\frac1{(k+1)^2}\leqslant\frac2{k^3}\leqslant\frac1{(k-1)^2}-\frac1{k^2}$$ yields $$\frac1{2(n+1)^2}\leqslant R_n\leqslant\frac1{2n^2}.$$ From here, one sees that the RHS is a simple equivalent of $R_n$ when $n\to\infty$. More generally, for every $\alpha\gt0$, ...


1

Use the theorem: if $x_n \sim y_n > 0$ and $\sum x_n < \infty$ then $$\sum_{n=N}^\infty x_n \sim \sum_{n=N}^\infty y_n $$ Let $$u_n= \frac1{2n^2}$$ Then check that $u_n - u_{n+1}\sim \frac1{n^3}$ (you can find such a relation looking for a $u_n$ in the form $u_n = \frac a{x_m}$). Hence $$ \sum_{n=N}^\infty \frac 1{n^3}\sim u_N = \frac 1{2N^2} $$ ...


1

Another comment that is too long to be a comment: The heuristic reason that the function is asymptotically proportional to $\sqrt{x}$ is that for very large $x$, $\cdot$ The contributions of the terms in $S_n(x)$ for $n$ much less than $\sqrt{x}$ behave as pseudo-random numbers, restricted to $[-1,1]$. Thus $S_n(x)$ for $n << \sqrt{x}$ can be ...


1

For the notation to make sense, it is sufficient that both are defined in a neighbourhood $\infty$ (the point of interest here), i.e. both domains must contain an interval $(x_0,\infty)$. Hence we can say things like $\ln x = O(x)$ $\frac1{x^2+1}= O(\sqrt x)$ But can one also say $42 = O(\tan^2x+1)$? One may argue that in those places where ...


1

Okay, I think I now understand what you are saying. I'll enumerate my responses for readability. 1) You said "$x−y={a\over b}$ if and only if either $x$ and $y$ are both rational or irrational." This is not true. See the excellent answer here: The sum of irrationals is irrational? 2) The notion of growing 'irrationally' or 'rationally' is undefined. You ...


1

Some basic facts that will help you: $(\log n)^c = O(n^d)$ for any $c,d > 0$. You can prove this with basic calculus. Also $n^d = O(c^n)$ for any $d > 0$ and $c > 1$ (also can be shown with calculus).


1

Hint: if $\lim t-x(t)=0$, then there exist "arbitrary large values" such that $x'(t)\geq 1/2$. However for sufficiently large $t$, if $t-x(t)\leq 1$ (which forces $x(t)\geq t/2$), then $x'(t)\leq 1/(1+t^2+t^2/4)\ll 1/2$...


1

Let $u(t) = x(t) - t$. Then the equation becomes $$ \left\{ \begin{array}{c} \frac{du}{dt} = 1 - \frac{u}{1+2t^2 + 2tu + u^2}\\ u(1) = 0 \end{array} \right. $$ Then since the denominator $1+2t^2 + 2tu + u^2$ is always positive (and in fact greater than 1),$$\lim_{t \rightarrow \infty} u(t) = 0 \ \Rightarrow \lim_{t \rightarrow \infty} \frac{du}{dt} = 1$$ ...


1

Forget about master theorem a minute. The hypothesis clearly states that $T(2^n) = T(0)$. Now if you assume htat $T$ increasing, you get $$ T(0)\le T(n) \le T(2^n) = T(0)\implies T(n) = T(0) $$hence $T$ is constant. So why bother with the big theorem? for practice purpose: $$ T(n)= T(n/2) $$ is the case 1 of the wiki article: $$ T(n) = aT(n/b) + f(n) ...


1

Here is how to get an upper bound, you can use similar reasoning to get the lower bound. First establish that $T(1)=0$ by algebraic manipulation, then note that $T(n)$ is monotonically increasing for $n\ge 1$. Thus we can get that for all $n$ greater then or equal to one we have: $T(\lfloor{n}\rfloor)\leq T(n)$ which gives us: $$T(\lfloor{n}\rfloor)\leq ...


1

$$\frac{1}{1 + \frac{1}{N}}=\frac{N}{N+1}\ne\frac{1}{N+1}\qquad(N\ne1)$$


1

The author didn't make a mistake, you just hadn't notice he "skipped" a step $\frac{1}{1+\frac{1}{N} } = \frac{N}{N+1} = 1-\frac{1}{N+1} $ Combined with the results you provided you get the desired result.


1

For positive $a$: $$ \sqrt{a^2 + 4} = a\sqrt{1+\frac{4}{a^2}} $$ and $$\lim_{a\to\infty}\sqrt{1+\frac{4}{a^2}} = 1. $$ So, the Taylor series of $\sqrt{1+x}$ around $0$ (when $x\to 0$) is: $$ \sqrt{1+x} = 1 + \left.\frac{1}{2\sqrt{1+x}}\right\rvert_{x=0} x + O(x^2) = 1+ \frac{x}{2} + O(x^2) $$ So, when $1<<a$ (it's important for $a$ to be big!) and ...


1

$f(n)\in o(n)$, hence $f(n)\leq n/h(n)$ for some function $h(n)\to +\infty$. Thus $h(n)\geq 2$ for any large $n$. Take $g(n)=e^n$: $g(f(n))\leq e^{n/2}\in o(e^n/n)$.


1

$$\log \left| \frac{f(x)}{g(x)} \right| = \log \frac{|f(x)|}{|g(x)|} = \log |f(x)| - \log |g(x)|$$


1

Take logarithms. $\alpha$ can be any negative number; if you are interested in $n\gg-\alpha$, then $\ln(n+\alpha)\approx\ln n+(\alpha/n)$, so $$ \ln C_n\approx (n-\alpha-\frac12)(\ln n+\alpha/n)-(n+\frac12)\ln n+n-\ln(2\pi)/2\\ \approx(-\alpha-1)\ln n+n+\alpha-\ln(2\pi)/2\\ C_n\approx\frac{1}{\sqrt{2\pi}}n^{-\alpha-1}e^{n+\alpha}$$


1

$f(x)$ is a $O(x^n)$ iff $|f(x)|\leq M|x^n|$ for any sufficiently large $x$. Hence a) $f(x)\in O(x^4)$, but $f(x)\notin O(x^3)$ ...



Only top voted, non community-wiki answers of a minimum length are eligible