Tag Info

Hot answers tagged

4

For every prime $p\le n$, there is at most $1$ number in $S$ divisible by $p$. So taking $S$ to be $1$ together with all the primes $\le n$ maximizes the size of $S$ subject to pairwise coprimality. Now the Prime Number Theorem gives us the asymptotics. Remark: One can characterize all maximum-sized subsets $S$ of $\{1,2,\dots,n\}$ such that any two ...


4

A proof I found a while ago entirely relies on creative telescoping. Since $\frac{1}{n^2}-\frac{1}{n(n+1)}=\frac{1}{n^2(n+1)}$, $$\begin{eqnarray*} \sum_{n\geq m}\frac{1}{n^2}&=&\sum_{n\geq m}\left(\frac{1}{n}-\frac{1}{(n+1)}\right)+\frac{1}{2}\sum_{n\geq m}\left(\frac{1}{n^2}-\frac{1}{(n+1)^2}\right)\\&+&\frac{1}{6}\sum_{n\geq ...


4

Here's one way to get a lower bound that grows exponentially. Start with the subset $S = \{n+1, \ldots, 2n\}$. Take an arbitrary subset $J \subseteq \{j \in S:\; j \text{ even},\; j > 4n/3\}$ and replace each $j \in J$ by $j/2$. This gives $2^{1 + \lfloor (n-1)/3 \rfloor}$ solutions. EDIT: For the second question: of course $f(n)$ is at most the ...


3

The claim is clearly wrong. For example let $f(n)=\frac1{n^2}$ and $g(n)=\frac 1n$ and $c=1$.


3

Stirling's approximation gives $$\binom{2n}{n} = \frac{(2n)!}{n!^2} \sim \frac{\sqrt{2\pi \cdot 2n} \left( \frac{2n}{e} \right)^{2n}}{\left[\sqrt{2\pi n} \left( \frac{n}{e} \right)^n \right]^2} = \frac{2\sqrt{\pi n} \cdot 2^{2n} \cdot \left( \frac{n}{e} \right)^{2n}}{2 \pi n \cdot \left( \frac{n}{e} \right)^{2n}} = \frac{1}{\sqrt{\pi n}} 2^{2n}$$


2

Yes, $n^3$ grows asymptotically faster than $2n^2\log n$, so $n^3$ is $\Omega(n^2\log n)$. This is the same as saying that $n^2\log n$ is $O(n^3)$, which should be well known -- since $n>\log n$ for all $n>0$, we have $n^3 \ge n^2\log n$ even before taking asymptotics.


2

I don't know what is $\Omega$, but a classical result says that $n^2\log n=o(n^\alpha)$ for all $\alpha>2$ (hence $n^2\log n=O(n^\alpha)$. As for your assertion, $n=o(n\log n)$, not $O$.


2

The Taylor expansion is for $$ φ(t,y(t),h)−φ(t,y(t)−s,h)=\frac{∂}{∂y}φ(t,y(t),h)s+O(s^2) $$ where $s=e_p(t)h^p$ so that $O(s^2)=O(h^{2p})$.


2

You take the most significant term, which is $3^{n+1}/2$. That turns out to be $3/2 \cdot 3^n$, so the expression is $O(3^n)$.


2

Remember that $O(x^p)\subset O(x^q)$ whenever $p\leq q$ (assuming Big-O is understood as $x\rightarrow\infty$). In other words, statements like $f(x)=O(x)+O(x^2)$ are redundant; we can just write $f(x)=O(x^2)$.


1

A linear recurrence of first order, which can always be "solved" (as long as finding closed forms of some ugly sums is possible). The general form is: $$ a_{n + 1} = f(n) a_n + g(n) $$ where $a_0$ is given. Divide by the summing factor: $$ S_n = \prod_{0 \le k \le n} f(k) $$ Note this is valid as long as $f(k) \ne 0$ over the relevant range. Thus: ...


1

Use Leighton's version of the master theorem: Consider a recurrence of the form: $$ T(z) = g(z) + \sum_{1 \le k \le n} a_k T(b_k z + h_k(z)) $$ fo $z \ge z_0$, $a_k$ and $b_k$ constants, with the restrictions: There are enough base cases For all $k$, $a_k > 0$ and $0 < b_k < 1$ There is a constant $c$ such that $g(z) = O(z^c)$ when $z \to \infty$ ...


1

$$\begin{align*}\int_{0}^{+\infty}\frac{\cos(nx)}{\cosh x}\,dx &= 2\sum_{m\geq 0}(-1)^m \int_{0}^{+\infty}\cos(n x)e^{-(2m+1)x}\,dx\\&=2\sum_{m\geq 0}\frac{(-1)^m (2m+1)}{n^2+(2m+1)^2}\\&=\frac{\pi}{2}\,\sech\frac{\pi n}{2}\end{align*}$$ since: $$ \text{Res}\left(\sec\frac{\pi z}{2},z=2m+1\right)=\frac{2}{\pi}(-1)^{m+1} $$ hence it follows that: ...


1

Since for all $a,b > 0$ we have $(\log n)^{a} = o(n^{b})$ as $n$ grows, so $n^{1/4} > \log n$ for large $n$, i.e. $n > n^{3/4}\log n$ for large $n$. If $f(n) = O(n^{3/4}\log n)$ as $n \to \infty$, then there is some $M \geq 0$ such that $|f(n)| \leq Mn^{3/4}\log n < Mn$ for large $n$, so $f(n) = O(n)$.


1

You can get the upper bound by $$1^p + 2^p + ... + n^p \le n^p + n^p + ... + n^p = n \ n^p = n^{p+1}$$ and you can get the lower bound by doing a similar thing after throwing away the first half of the sum $$1^p + ... + (\frac n 2)^p + ... + n^p \ge (\frac n 2)^p + ... + n^p \ge (\frac n 2)^p + ... + (\frac n 2)^p = \frac n 2 \ (\frac n 2)^p = {(\frac n ...



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