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.

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

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


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

  • $\begingroup$ Oh, so it suffices to show that $lim_{n \to \infty} \frac{n^k}{b^n}=0$? (with $b\geq1$) $\endgroup$ – JSullivan Jan 5 '13 at 23:49
  • $\begingroup$ @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). $\endgroup$ – Brian M. Scott Jan 5 '13 at 23:56
  • $\begingroup$ @JSullivan: You’re welcome! $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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