Hot answers tagged

3

As you said you need to check if there is a constant $C>0$ such that $n! \le C 2^n$ for all $n$ (or at least all sufficiently large $n$, but it does not matter much). Note it is crucial that $C$ does not depend on $n$. In this case it turns out there is no such $C$. There are various ways to see this. One of them could go like this. Assume there is ...


2

Comparing $f(n)=n^{1/10}$ and $g(n)=(\log n)^{10}$ may be done more informally by studying what happens when you square $n$: $f$ is squared, while $g$ is multiplied by $1024$. Clearly $f$ will eventually overtake any constant multiple of $g$ by repeatedly squaring the argument.


1

From the usual limit $\dfrac{\log n}{n} \mathop{\longrightarrow}\limits_{n \rightarrow +\infty} 0$ you can get $\dfrac{(\log n)^a}{n^b} \mathop{\longrightarrow}\limits_{n \rightarrow +\infty} 0$ for any $a > 0$ and $b > 0$. So you don't have $n^\frac{1}{10} \in O((\log(n)^{10})$ but on the contrary $(\log n)^{10} \in O(n^\frac{1}{10})$.


1

Hint: $$ \frac{n^{1/10}}{(\log n)^{10}} = \left(\frac{n^{1/100}}{\log n} \right)^{10} $$


1

You're starting with a function $g$ which is bounded below by a function $f$. If you multiply that function $f$ by $n^2$, do you think it will necessarily be larger than $g$ afterward? What if $f$ is much smaller than $g$?


1

A simple proof without induction: suppose there exists a constant $C>0$ such that $n!\le 2^n$. Note $n!\ge2^{n-1}$ for all $n\ge 1$, hence for all $n>1$, $$n=\frac{n!}{(n-1)!}\le \frac{C2^n}{2^{n-2}}=4C$$ from which we conclude that $\mathbf N$ is bounded from aboveā€¦


1

It is not. Intuitively, $n!$ has $n$ factors and most of them are larger than $2$. The ratio gets larger and larger, so you should expect $\frac {n!}{2^n}$ to grow without bound. A very simple proof by induction is that $\frac {4!}{2^4} \gt 1$. Assume $\frac {k!}{2^k} \gt 1,$ then $\frac {(k+1)!}{2^{k+1}} \gt \frac {k+1}2$ which grows without bound.


1

Divide both numerator and denominator by $\frac{1}{2}x$: $$g(x)=\frac{1+\frac{1}{4}x+O(x^2)}{1-\frac{1}{4}x+O(x^2)}$$ Use the fact that $\frac{1}{1-u} = 1+u + O(u^2)$ when $u\to 0$: $$g(x)=\left({1+\frac{1}{4}x+O(x^2)}\right)\left({1+\frac{1}{4}x+O(x^2)}\right)$$ Expand, stopping at the $x^2$ order (since you have an $O(x^2)$): ...


1

For all $d \geq e$ and $0 < p < 1$ the equation $$ N^d = pe^N $$ has two positive solutions $N$, call them $N_1$ and $N_2$. Since the maximum of $x \mapsto x^d e^{-x}$ occurs at $x=d$ and $x^d e^{-x} \to 0$ as $x \to \infty$ we know that $N_1 < d < N_2$. We'll first investigate the behavior of $N_1$, then $N_2$ afterwards. Because the maximum ...


1

You can get through a lot of the complication by scaling. For example, let $y=x u$; then $$F(x) = x \int_0^1 du \frac{(1-x^3 u^3)^a}{\displaystyle \sqrt{\left (\frac{1-x^3 u^3}{1-x^3}\right )^b-u^4}} $$ It should be plain to see that $$F(x) \sim x \int_0^1 \frac{du}{\sqrt{1-u^4}} = \frac{\Gamma^2\left ( \frac14 \right )}{4 \sqrt{2 \pi}} x \quad (x \to ...


1

Suppose we seek to evaluate $$S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k {k\choose j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}.$$ This is $$S(N) = \sum_{n=N}^\infty \frac{t^n}{n!} \sum_{k=N}^n \sum_{j=0}^k {k\choose j} (-1)^{k-j} (1+j)^n.$$ Now introduce $$(1+j)^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((1+j)z) \; dz.$$ We ...



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