Baby Rudin: Theorem 3.20 (c) and (d)

Question

In theorem 3.20, Rudin offers a proof to the limits of the following sequences: $$u_n = n^{\frac{1}{n}}$$ $$v_n = \frac{n^{\alpha }}{(1+p)^n}$$ with $\alpha$ a real number and $p > 0$.

In both the proofs, Rudin uses inequalities which I am not familiar with. For $u_n$, the following inequality is used:

$$(1+x)^n \ge \frac{n(n-1)}{2}x^2$$

For $v_n$: $${n \choose k}p^k > \frac{n^kp^k}{2^kk!}\quad \quad(n>2k) $$

I have painstakingly come up with proofs for both of those inequalities, however, and this is especially true for the second inequality, my proofs are not very elegant nor do they give me any idea of the inequality came to be.

Surely Rudin doesn't pull these inequalities out of thin air. Where can I find a more comprehensive derivation of these inequalities? Where do they come from exactly (which field)?

---

Update:

Here are my proofs. They both rely on induction. For the first one:

Suppose $x\ge0$. Then, for $n = 2$: $$ (1+x)^2 = 1+2x+x^2 $$ $$\frac{2(2-1)}{2} x^2 = x^2$$ Since $x\ge0$, we have $(1+x)^n \ge \frac{n(n-1)}{2}x^2 $ for n = 2.

Suppose our inequality is true for a certain n. Then: $$ (1+x)^n + nx^2 \ge \frac{n(n+1)}{2}x^2$$

Let $D = (1+x)^{n+1} - (1+x)^n - nx^2 $. Since $\forall n \in \mathbb{N}, \forall m = 0,1, ... n, {n+1 \choose m} \ge {n \choose m} $, and ${n+1 \choose 2} - {n \choose 2} - n = 0$, we have:

$$D \ge 0 \Rightarrow (1+x)^{n+1} \ge (1+x)^n + nx^2$$ So: $$(1+x)^{n+1} \ge \frac{n(n+1)}{2}x^2$$ The theorem follows by induction.

For the second inequality: We want to prove that $n(n-1)...(n-k+1) > \frac{n^k}{2^k}$, with $n > 2k$

Let $n\in\mathbb{N}, k$ and integer greater than 0 such that $2n > k$. Then for $k=1$, we have: $$n > \frac{n}{2} $$

Now suppose our inequality holds for a certain $k$. Then:

$$n(n-1)...(n-k+1)(n-k) > \frac{n^k}{2^k}(n-k)$$ Since $n > 2k$, $n-k > \frac{n}{2} > 0$ such that: $$n(n-1)...(n-k+1)(n-k) > \frac{n^k}{2^k}(n-k) > \frac{n^{k+1}}{2^{k+1}} $$

By induction, our inequality holds for all $k$ such that $n > 2k$

Answer 1

For the first one, assuming $x\geq0$ :

$$ \begin{align} (1+x)^n &= \sum_{k=0}^n \binom{n}{k}x^k \\ &=1+nx+\frac{n(n-1)}{2}x^2+\cdots+x^n \\ &\geq \frac{n(n-1)}{2}x^2 \end{align} $$

For the second one :

$$ \begin{align} \binom{n}{k}&= \frac{n(n-1)\cdots(n-k+1)}{k!} \\ &=\frac{1\left(1-\frac{1}{n}\right)\cdots\left(1-\frac{k-1}{n}\right)}{k!}n^k \\ &>\frac{(1/2)(1/2)\cdots(1/2)}{k!}n^k \\ &=\frac{n^k}{2^kk!} \end{align} $$

Answer 2

The first inequality can be derived, for $x\ge0$, from the binomial theorem: $$ (1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k $$ If we remove all the (non negative) terms except the one for $k=2$, we get $$ (1+x)^n\ge \binom{n}{2}x^2 $$

Answer 3

Prove that the sequence $v_n = \frac{n^{\alpha }}{(1+p)^n}$ goes to $0$, where $p \gt 0$ and $\alpha$ is any real number.

It might be helpful to examine what this is saying before jumping into the proof. To give $v_n$ a tough time (of going to $0$), think of a really big $\alpha$, like $10^6$, and keep $p$ small, like $10^{-6}$ (a big numerator and a small denominator). Proving (d) is showing that exponential growth (denominator) trumps 'polynomial' growth (numerator). Instead of $(1+p)^n$ in the denominator, why didn't Rudin use $\beta^n$ with $\beta \gt 1$? Ans: He knew that he wanted to 'crank out' a 'polynomial type thing' for an exponential.

Now, it only gets interesting when $\alpha$ is large, so naturally we are hoping that by taking an integer $k \gt \alpha$ we can make some headway. Also, if you expand $(1 + p)^n$ you are hoping to find a single term that does the trick. Considering the shape of Pascal's Triangle, the big number 'meat' should be found in the middle. So the first thing to try is letting $n$ to be twice as big as $k$.

So, by inspection, if $n = 2k$,
${2k \choose k} \gt \frac{k^k}{k!} = \frac{(2k)^k}{2^k k!} = \frac{n^k}{2^k k!} $

These are some of the tactics behind the terse proof supplied by Rudin.

Answer 4

Let $f(x)=(1+x)^n-1-\frac{n(n-1)}{2}x^2$, where $x\geq0$.

For $n=1$ we see that $f(x)\geq0$.

But for $n\geq2$ we obtain: $f''(x)=n(n-1)(1+x)^{n-2}-n(n-1)\geq0$, which gives

$f'(x)=n(1+x)^{n-1}-n(n-1)x\geq f'(0)>0$ and $f(x)\geq f(0)=0$ and we are done!