Tag Info

Hot answers tagged

2

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}\,dt$$ This 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))}$$



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