Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm working with this problem but I have no idea how to solve it. Here $k$ is fixed and $0<a<1$.

I was trying to use that $\lim_{n \to \infty} a^n =0$ and that $\binom{n}{k}\leq\frac{n^k}{k!}$ with the $\epsilon$ definition to prove it, my intention was to show that for $N$ large enough $a^N < \frac{k!}{N^k}$ but I got nowhere. I don't know if using the definition is the best aproach.

share|improve this question
    
I assume that you mean the limit as $n\to\infty$. –  Brian M. Scott Jan 5 '13 at 23:16
    
Yes, sorry for the typo –  JSullivan Jan 5 '13 at 23:19

2 Answers 2

up vote 8 down vote accepted

HINT: Let $$p(x)=\frac{x(x-1)(x-2)\dots(x-k+1)}{k!}\;;$$ this is a polynomial of degree $k$, and $p(n)=\binom{n}k$ for $n\in\Bbb N$. Now

$$\lim_{n\to\infty}\binom{n}ka^n=\lim_{n\to\infty}\frac{p(n)}{(1/a)^n}\;,$$

where the numerator grows polynomially, and the denominator grows exponentially.

share|improve this answer
    
Oh, so it suffices to show that $lim_{n \to \infty} \frac{n^k}{b^n}=0$? (with $b\geq1$) –  JSullivan Jan 5 '13 at 23:49
    
@JSullivan: Almost. You need $b>1$, and you you need an arbitrary polynomial of degree $k$ in the numerator. That last is no problem, however: if $C$ is the maximum absolute value of any coefficient of $p(x)$, $p(n)\le C(k+1)n^k$ for all $n$ (since $p$ has $k+1$ terms). –  Brian M. Scott Jan 5 '13 at 23:56
    
Thanks, that was very helpful! –  JSullivan Jan 6 '13 at 0:02
    
@JSullivan: You’re welcome! –  Brian M. Scott Jan 6 '13 at 0:04

Let $t_n$ be the $n$-th term. Calculation shows that $$\frac{t_{n+1}}{t_n}=\frac{\binom{n+1}{k}a^{n+1}}{\binom{n}{k}a^n}=\frac{n+1}{n+1-k}a=\left(1+\frac{k}{n+1-k}\right) a.$$ If $n$ is large enough, $\left(1+\frac{k}{n+1}\right)a \lt b$, for some fixed $b\lt 1$. So after a while, each time we increment $n$ by $1$, $t_n$ decreases by a factor of at least $b$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.