Tag Archives: inequalities

A new AM-GM inequality

I recently found the following inequalities useful:

\displaystyle \left(x+\frac{a_1+\cdots+a_n}{n}\right)^n\ge (x+a_1)\cdots(x+a_n)\ge \left(x+\sqrt[n]{a_1\cdots a_n}\right)^n,

for any x,a_1,\dots,a_n\ge 0.

To prove the left half simply apply AM-GM to the product

\displaystyle (x+a_1)\cdots (x+a_n)\le \left(\frac{(x+a_1)+\cdots+(x+a_n)}{n}\right)^n.

The right half follows directly from Hölder’s inequality.

More generally, one has

\displaystyle\left(\frac{a_1+\cdots+a_n}{n}+\frac{b_1+\cdots+b_n}{n}\right)^n\ge (a_1+b_1)\cdots(a_n+b_n)\\\ge \left(\sqrt[n]{a_1\cdots a_n}+\sqrt[n]{b_1\cdots b_n}\right)^n

for a_1,\dots,a_n,b_1,\dots,b_n\ge 0. The proof goes similarly.

One obtains similar inequalities for any number of vectors a,b,c,\dots.


As an example, for a_i=i we get the inequalities

\displaystyle \left(x+\frac{n+1}{2}\right)^n\ge (x+1)\cdots (x+n)>\left(x+\frac ne\right)^n

using the fact that \sqrt[n]{n!}/n\to 1/e from above.

Advertisements

Leave a comment

Filed under Algebra

Another inequality involving sigma and tau

cf. an inequality involving sigma and tau.

Let n be a positive integer. By the weighted AM-GM inequality, one has

\displaystyle\frac{\sum d\cdot n/d}{\sum n/d}\ge\left(\prod d^{n/d}\right)^\frac{1}{\sum n/d},

where all sums and products are taken over the positive divisors d of n. This means

\displaystyle\boxed{\frac{n\tau(n)}{\sigma(n)}\ge\left(\prod_{d\mid n}d^{1/d}\right)^{n/\sigma(n)}}.

Considering the analytic behaviour of the function f(x)=x^{1/x} one deduces

\displaystyle\prod_{d\mid n}d^{1/d}\ge\prod_{1\neq d\mid n}n^{1/n}=n^{(\tau(n)-1)/n}

for any n, with equality iff n is prime or 1 or 4. (By convention we take an empty product to be 1.) Combining this with the first inequality in this post we obtain

\displaystyle n^{1/2}\ge\frac{n\tau(n)}{\sigma(n)}\ge n^\frac{\tau(n)-1}{\sigma(n)},

i.e.,

\boxed{\displaystyle n^{1/2}\le\frac{\sigma(n)}{\tau(n)}\le n^{1-\frac{\tau(n)-1}{\sigma(n)}}}.

This strengthens the first boxed inequality from this post.

Leave a comment

Filed under Number theory

An inequality involving sigma and tau

Let \tau(n) and \sigma(n) respectively be the number and the sum of the positive divisors of the positive integer n. We will prove the following inequality:

\sigma(n)\ge \sqrt n\tau(n).

First proof. By the Cauchy-Schwarz inequality,

\displaystyle\sigma(n)^2=\left(\sum_{d\mid n}d\right)\left(\sum_{d\mid n}\frac nd\right)\ge (\sqrt n\tau(n))^2=n\tau(n)^2.

Second proof. By Chebyshev’s inequality,

\displaystyle\sigma(n)^2=\left(\sum_{d\mid n}d\right)\left(\sum_{d\mid n}\frac nd\right)\ge \tau(n)\cdot n\tau(n).

Third proof. By the AM-GM inequality,

\displaystyle 2\sigma(n)=\sum_{d\mid n}\left(d+\frac nd\right)\ge 2\sqrt n\tau(n).

Fourth proof. Again by the AM-GM inequality,

\displaystyle n^{\tau(n)}=\prod_{d\mid n}d\prod_{d\mid n}n/d=\left(\prod_{d\mid n}d\right)^2\Rightarrow n^{\tau(n)/2}=\prod_{d\mid n}d\le\left(\frac{\sigma(n)}{\tau(n)}\right)^{\tau(n)}.

Fifth proof. If n=p_1^{a_1}\cdots p_k^{a_k} factored into primes, then AM-GM gives

\displaystyle\sigma(n)=\prod_{j=1}^k(p_j^{a_j}+\cdots+p_j+1)\ge\prod_{j=1}^k(a_j+1)p_j^{a_j/2}=\sqrt{n}\tau(n).

We also trivially have \sigma(n)\le n\tau(n). Hence for all n,

\displaystyle \boxed{\sqrt n\le\frac{\sigma(n)}{\tau(n)}\le n}.

In general, if f:\mathbb N\to\mathbb N is completely multiplicative, and

F(n):=\displaystyle\sum_{d\mid n}f(d),

then the first four proofs can be generalised to deduce that

(*)\qquad\qquad\qquad\qquad\quad\ F(n)\ge \tau(n)\sqrt{f(n)}.

For example, if \sigma_k(n) is the sum of the k-th powers of the positive divisors of n, then this shows that

\displaystyle \boxed{n^{k/2}\le\frac{\sigma_k(n)}{\tau(n)}\le n^k}

for each k\ge 0. This, combined with the result from the previous post, gives

\displaystyle\lim_{n\to\infty}\frac{\sigma_k(n)}{n^{k+1}}=0,

i.e., \sigma_k(n)=o(n^{k+1}) as n\to\infty, for each k\ge 0.

1 Comment

Filed under Number theory