0
votes
1answer
33 views

Inequality with little-o notation

I'm having trouble justifying the following: For large $n$, \begin{align*} -\log f(n) & < \log n + o(\log n)\\ \implies f(n) &> n^{-1} \log^3(n) \log(10) \end{align*} I think basically ...
1
vote
1answer
32 views

Clarification: how to get the following asymptotics

I'm having some trouble justifying some steps in a paper. Let $a_n$ be an increasing sequence of integers satisfying $n! \le a_n \le 2(n!)$, and let $f:\mathbb{N} \to \mathbb{N}$ be a function ...
1
vote
1answer
31 views

Computational complexity and the big $\mathcal{O}$

I have a question about this Big $\mathcal{O}$ problem. I have the question down $90\%$, but the other $10\%$ isn't getting to me. I will write out the entire question and I'll point out the step, ...
0
votes
0answers
47 views

Little o notation inequalities involving $n^{\log n}$

Apologies as this is a minor re-post, but I didn't think the other would get answers as it diverged into a discussion and got pushed down... I'm struggling with asymptotic notation a little bit... ...
6
votes
3answers
143 views

Asymptotic behaviour of the integral of the quadratic mean of the coordinates on the hypercube

I have to compute the limit $\lim_{n\to +\infty}I_n$, where: $$\qquad I_n=\int_{[0,1]^n}\sqrt{\frac{1}{n}\sum_{i=1}^n x_i^2}\,d\mu.$$ I believe that its value is just $\frac{1}{\sqrt{3}}$, since the ...
0
votes
0answers
50 views

Help inequality with $O(\cdot)$ and $\Omega(\cdot)$

Suppose,$$f(T)\le O\left(\sqrt{\dfrac{\log( T/\delta)}{T}}\right).$$ If we let $\delta=\dfrac{1}{n^2}$ and $T\ge\Omega\left(n^2\log n\right)$, then: $$f(T)\le \dfrac{1}{n}.$$ Can anyone ...
4
votes
1answer
50 views

On the sum of relatively prime number $<N$

Let $A(N)$ be a function which is the sum of all numbers relatively prime and $<N$ and $B(N)$ the sum of remaining $N−\phi(N)$ numbers. Then I have the following questions- Q-1 For what values of ...
0
votes
0answers
31 views

Question about picking value large enough so that an inequality holds for all values larger than said value

This question makes me wonder about more general inequalities, but I have a particular example. Let $C$ be a positive fixed constant, $0<\epsilon<1$ be given, and assume $\alpha,\beta\in ...
11
votes
6answers
398 views

Asymptotic behaviour of a multiple integral on the unit hypercube

A few days ago I found an interesting limit on the "problems blackboard" of my University: $$\lim_{n\to +\infty}\int_{(0,1)^n}\frac{\sum_{j=1}^n x_j^2}{\sum_{j=1}^n x_j}d\mu = 1.$$ The correct claim, ...
8
votes
3answers
108 views

Sum $S(n,c) = \sum_{i=1}^{n-1}\dfrac{i}{ci+(n-i)}$

Consider the sum $$S(n,c) = \sum_{i=1}^{n-1}\dfrac{i}{ci+(n-i)}$$ where $0\le c\le 1$. When $c=0$, $S(n,c)$ grows asymptotically as $n\log n$. When $c=1$, $S(n,c)$ grows asymptotically as $n$. ...
5
votes
1answer
147 views

How to prove this inequality $\pi(x) > \log x - 1$ involving the prime counting function?

Problem Prove that $\pi(x) > \log x - 1$. Progress Based on a hint and very elementary methods, I got that $$ \prod_{p \leq x} (1-p^{-1})^{-1} \leq \prod_{k=2}^{\pi(x)+1} (1-k^{-1})^{-1}. $$ The ...
0
votes
0answers
46 views

Proving a Certain Inequality that Involves the Sinc Function

Could someone kindly show me how to rigorously prove that there exists a constant $ C > 0 $ such that $$ \forall N \in \mathbb{N}: \quad \sup_{x \in \mathbb{R}} \sum_{\substack{k \in \mathbb{Z} \\ ...
5
votes
0answers
92 views

Binomial asymptotic.

Is there any "direct" proof of the following asymptotic inequality: let $\alpha\le 1$ and consider $$Q_n(x)=\sum_{k=1}^n\frac{\alpha(\alpha+1)(\alpha+2)\cdots(\alpha+k-1)}{k!}x^k$$ Then, $$\int_0^1 ...
0
votes
2answers
94 views

Asymptotic equality and inequalities

If $f$ equals $g$ asymptotically, i.e., $f(x)/g(x) \to 1$ (as $x \to \infty$), and $h \leq f$, does that mean $h \leq g$ for sufficiently large $x$? It seems to be true because the relative error, ...
7
votes
1answer
84 views

An asymptotic integral inequality

Suppose $f:\mathbb{R}\to\mathbb{R}$ is a continuous function, $g(x)=xf(x)-\int_0^xf(t)\ dt$, and we have $f(0)=0$ and $g(x)=O(x^2)$ as $x\to0$. Is it true that $f(x)=O(x)$ as $x\to0$ ?
1
vote
1answer
363 views

Bounding the modified Bessel function of the first kind

i'm looking for an upper bound for the modified Bessel function of the first kind of a +ive real argument. It seems that it satisfies the inequality : $$I_{n}(x)\leqslant \frac{x^{n}}{2^{n}n!}e^{x}$$ ...
8
votes
3answers
449 views

the following inequality is true, but I can't prove it

The inequality $$\sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right)$$ holds for all integer $d\geq 1$. I use computer to verify it for $d\leq 50$, and find ...
0
votes
1answer
24 views

Is $(1+1/(x-1))^{x^\delta} > 2$ when $x > 1$ and $\delta \ge 1$?

Let $\delta>0$ be some fixed real number. I am interested in how $$(1+1/(x-1))^{x^\delta}$$ behaves when $x > 1$. In particular, I would like to know if $$(1+1/(x-1))^{x^\delta} > 2$$ holds ...
2
votes
1answer
47 views

A number-theoretical estimation-inequality

I have some trouble understanding the following number-theoretical estimation: $$\sum_{k\le \sqrt{n}} (1-k^2/n)^{1+o_n(1)}=n^{1/2+o(1)} \ (n\to\infty),$$ where $o_n(1)$ denotes a $o(1)$ function ...
4
votes
0answers
76 views

Dominated convergence on $e^{-n^2 t} t^{s/2-1}$

I am trying to apply the Dominated Convergence Theorem to show that $$\sum_{n\ge 1} \int_0^1 e^{-n^2 t} t^{s/2-1}dt= \int_0^1 \sum_{n\ge 1}e^{-n^2 t} t^{s/2-1}dt$$ as soon as $s>1$. I've ...
1
vote
1answer
147 views

Inequality for binomial coefficients

Let $m \leq n, n \leq N$ and $0\leq k \leq m$. I am wondering what is the dependence of $n$ and $N$ that for all $m, k$ $$ \frac{{N-m \choose n-k}}{{N \choose n}}\leq 1. $$ Thank you for your help.
6
votes
1answer
148 views

Landau Notation Properties

I would like to take the limit $x\to 0$ and prove or disprove the following statements concerning Landau notation. (a) $O(x^{3/2})\subset o(x)\subset O(x^{1/2})$ (b) $(1+O(x))^2=1+O(x^2)$ I know ...
1
vote
0answers
326 views

Convergence of $L^p$ norms

Given a measure space $X$ with its measure $\mu$, it can be shown (I'll provide a proof if asked for) that $\displaystyle \forall f \in L^\infty(X,\mu),~\textrm{if } \exists p_0:\forall q \geq p_0, ...
1
vote
1answer
112 views

Theta notation from the inequality $c_1lg(n) \leq lg(k) \leq c_2lg(n)$ [duplicate]

Possible Duplicate: tight bounds from a certain inequality Consider the inequality $$ c_1lg(n) \leq lg(k) \leq c_2lg(n),\text{ for } n \geq n_{0} $$ With $c_1,c_2,n_0 > 0$, $lg(k) = ...
2
votes
1answer
658 views

Proof of Chebyshev's theorem

(a) Show that $\int_2^x\frac{\pi(t)}{t^2}dt=\sum_{p\leq x }\frac{1}{p}+o(1)\sim\log\log x.$ (b) Let $\rho(x)$ be the ratio of the two functions involved in the prime number theorem: ...
1
vote
1answer
133 views

Why is this true for large enough n?

$$ \begin{align*} \Pr[\text{bin } i \text{ has at least } k \text{ balls}] &\leqslant \left( \frac{e}{k} \right)^k = \left( \frac{e \ln \ln n}{3 \ln n} \right)^{\frac{3 \ln n}{\ln \ln n}} ...
1
vote
1answer
110 views

Understanding a simplification in a theorem

I'm trying to understand a theorem in a paper on page 14/24. We are given that $$Z = (nq-1) \log \left(\frac{M+nq-1}{nq-1} \right) + M \log \left(\frac{M+nq-1}{M} \right) + \frac{1}{2} \log \left( ...
6
votes
1answer
157 views

Inequality on balls/bins with nested logs

Let $k = \lceil \frac{3 \ln n}{\ln \ln n}\rceil$. How does one show that $$ \left(\frac{e}{k}\right)^k \frac{1}{1-\frac{e}{k}} \le n^{-2} ? $$ This is from p. 44 of Motwani and Raghavan, Randomized ...
5
votes
3answers
746 views

How to solve $n < 2^{n/8}$ for $n$?

This is from an exercise (1.2.2) in introduction to algorithms that I'm working on privately. To find at what point a $n \lg n$ function will run faster than a $n^2$ function I need to figure out for ...