# Tag Info

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 ...
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 ...