Proof that $\lim_{n\rightarrow\infty}\frac{n^\alpha}{(1+p)^n}=0$ from Rudin's Principles of Mathematical Analysis, involving the binomial theorem

We are showing that when $\alpha$ and $p$ are real and $p>0$ then $$\lim_{n\rightarrow\infty}\frac{n^\alpha}{(1+p)^n}=0$$

Proof. Let $k$ be an integer such that $k>0$, $k>\alpha$. Then for $n>2k$,$$(1+p)^n> \binom{n}{k}p^k=\frac{n(n-1)\cdots(n-k+1)}{k!}p^k>\frac{n^k p^k}{2^k k!}$$ Hence for $n>2k$, $$0<\frac{n^\alpha}{(1+p)^n}<\frac{2^k k!}{p^k}n^{\alpha-k}$$

Since $\alpha-k<0$, $n^{\alpha-k}\rightarrow 0$.

I can follow the whole thing except for where the heck $2^k$ came from. It's clear that it has to do with the fact that the numerator of the big fraction is a product of $k$ terms involving $n$ and $n>2k$ but that's as far as I can see.

-

2 Answers

Look at the terms $n$, $n-1$, $n-2$, and so on up to $n-k+1$. There are $k$ terms in the list.

Each of these $k$ terms is $\gt \dfrac{n}{2}$. For the smallest one, which is $n-k+1$, is greater than $n-n/2+1$. Hence their product is $\gt \left(\dfrac{n}{2}\right)^k$.

-

I suspect that either Rudin or yourself made a typo, the leftmost term in your first displayed equation should be $(1+p)^n$.

The first inequality follows from considering only one term of the binomial expansion, and the second inequality comes from the observation that the numerator of the fraction consists of k terms, each larger than $(n-k+1)$, which is itself larger than $(n-n/2+1)>n/2$.

You should be able to finish it from here.

-
typo was all mine – crf Nov 16 '12 at 7:15