# Tag Info

Since $$\lim_{x\to+\infty}\frac{\log x}{x^a}=0$$ for $a>0$, we also get that (with $a=1/2$) $$\lim_{x\to+\infty}\frac{(\log x)^2}{x}=\lim_{x\to+\infty}\Bigl(\frac{\log x}{x^{1/2}}\Bigr)^2=0.$$ Now, let $x=\log n$, and you get $$\frac{\bigl(\log(\log(n))\bigr)^2}{\log n}\to 0\quad\text{as}\quad n\to+\infty.$$ Thus $$(\log ... 2 You need to decide whether (\log n)^{\log n} is polynomially bounded or not. For example, can you prove$$ (\log n)^{\log n} < n^5 $$for large enough n? 2 Yes. Note that f is a function not just of dimension but of the volume of the domain. 2 We write this as$$\sum_{p\le x}{\log n\over n^\alpha}\cdot 1_p$$From here we use partial summation to get$$\pi(x){\log x\over x^\alpha}-\int_1^x\pi(t){1-\alpha \log t\over t^{1+\alpha}}\,dt$$using the PNT and monotonicity of the integral, this is asymptotic to$$x^{1-\alpha}-\int_1^x {1-\alpha\log t\over t^\alpha\log t}\,dtThis gives ... 2 For all n \ge 1, we have 2n \le 2n^2 and 3 \le 3n^2. Therefore, 7n^2+2n+3 \le 7n^2+2n^2+3n^2 = 12n^2. 2 The O-notation doesn't mean anything for a fixed n, say: n:=1000. But it means something in the mental process n\to\infty. We have this \tau-sum which we try to understand, or estimate. And there is the simple and exact term g(n):=n(\log n+2\gamma -1) that we understand. Saying that the difference between this as yet mysterious sum and the term ... 2 Just let us see what we get if we expand T(n) = n⋅T(n-1) + n: \begin{align}T(n) &= n⋅T(n-1) + n\\ &= n⋅((n-1)⋅T(n-2) + n-1) + n\\ &= n⋅((n-1)⋅((n-2)⋅T(n-3) + (n-2)) + (n-1)) + n\\ &= n⋅(n-1)⋅(n-2)⋅T(n-3) + n⋅(n-1)⋅(n-2) + n⋅(n-1) + n\\ &= \sum_{k=1}^n \frac{n!}{k!} \end{align} Since n! is a summand of this ... 2 Hint: For intuition, try taking the limit of the ratio\lim_{n\rightarrow\infty}\frac{n2^n}{3^n}=\lim_{n\rightarrow\infty}n\left(\frac{2}{3}\right)^{n}$$1 There exists no such b even if f is symmetric and associative.Let f(x,y) be defined by$$f(x,y)=[(b(x,y)+b(y,x)+1).e^{x+y}]+1.1$$where [.] is greatest integer function if both x and y are natural numbers and f(x,y)=1.1 if any one of x,y fail to be a natural number.Notice that f(f(x,y),z)=f(x,f(y,z))=1.1 for all x,y,z since f(x,y) is ... 1 For c: due to \sin n this function is unbounded, so there doesn't exist c such that any of the order functions hold For e: consider taking n = e^t For f: use Stirling's formula or Euler-Maclaurin for \sum_k \log k, these functions are of the same order. 1 The best way that I'm aware of proving such a result is using a generalization of Laplace's method. The topic is introduced and this paper has an example of using it to obtain the general Stirling expansion. https://www.cs.elte.hu/blobs/diplomamunkak/msc_mat/2012/nemes_gergo.pdf 1 The first one is not too hard: g(n) \leq f(n) for every n, so f(n) = O(g(n)). To prove that g(n) \neq O(f(n)), let C>0 be arbitrary. Find n_0 so that (12/7)^{n_0} > C (how?). Then if n \geq n_0 then 12^n \geq C 7^n. For the second one, here's a hint: \log_9(n^4)=4 \log_9(n), \log_9(n^5)=5 \log_9(n). 1 Let f(n) := 7n^{2} + 2n + 3 for all integers n \geq 1. Then f(n)/n^{2} = 7 + 2/n + 3/n^{2}. We claim that there is a real M such that f(n)/n^{2} \leq M for large n. But both (2/n) and (3/n^{2}) are convergent to zero, so that 2/n, 3/n^{2} < 1/2 for large n, and hence 7 + (2/n) + (3/n^{2}) < 7 + 1 = 8 for large n. Letting M := ... 1 Use partial summation formula:$$\sum_{n\leq x}\sum_{d\mid n}\tau_{k}\left(d\right) = \sum_{d \le x} \tau_k(d)\left[\frac{x}{d}\right] = \mathcal{O}\left(x\int_1^x \frac{\log^{k-1} t}{t}\,dt\right) = \mathcal{O}\left(x\log^k x\right)$$1 The ceilings don't matter; \lceil f(n) \rceil \leq f(n)+1 \leq 2 f(n) provided f(n) \geq 1. So up to a constant factor you are dealing with \log(n)^{1/2} \log(n)^{\log(n)} (1/n). Here's a hint on how to manage that:$$\log(n)^{\log(n)} = \exp ( \log(n) \log(\log(n))) = n^{\log(\log(n))}
Hint: Consider $f(n)=n^2$ and $g(n)=n$.