5
$\begingroup$

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.

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

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2013 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$ Jan 5, 2013 at 23:56
  • $\begingroup$ @JSullivan: You’re welcome! $\endgroup$ Jan 6, 2013 at 0:04
2
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .