1

Proof-verification for $\lim\limits_{n\to\infty}\frac{1}{2^n}\cdot \binom nk$ for a fixed $k\in \mathbb{N}$

so that's how I solved it:$$\frac{1}{2^n}\cdot \binom nk=\frac{n!}{2^n \cdot k!(n-k)!}=\frac{n\cdot (n-1)\cdot \ldots \cdot k! \cdot \ldots \cdot (n-k+1)\cdot (n-k)! }{2^n \cdot k!(n-k)!}=\frac{n\cdot (n-1)\cdot \ldots \cdot (n-k+1)}{2^n} \overset{n\to\infty}\longrightarrow 0$$

since we know that exponential growth is way faster than polynomial growth...

Martin Sleziak
  • 53,687
Analysis
  • 2,450

3 Answers3

3

Noting that, for $n\ge k$, $$ 2^n=(1+1)^n\ge \binom{n+1}{k+1}=\binom{n}{k}\frac{n+1}{k+1} $$ one has $$ 0\le \frac{1}{2^n}\binom{n}{k}\le\frac{k+1}{n+1} $$ which implies $$\lim\limits_{n\to\infty}\frac{1}{2^n}\binom{n}{k}=0.$$

xpaul
  • 44,000
2

The idea of the proof is correct, but the proof is not rigorous because the factors of $\binom nk$ have been handled haphazardly. A more rigorous approach is to notice that since $k$ is fixed, $\binom nk$ is a $k$th degree polynomial (all but the first $k$ factors in $n!$ are removed by the division by $(n-k)!$, while $k$ is a fixed constant) and then to use the fact of exponential functions growing faster than all fixed-order polynomial functions, as before.

Parcly Taxel
  • 103,344
0

You are missing a factor $k!$ in your last expression. Also, you could make that last sentence more explicit by noting that the sequence is nonnegative and $$\frac{n\cdot (n-1)\cdot \ldots \cdot (n-k-1)}{2^n k!}\leq\frac{n^k}{2^n k!}\leq\frac{n^k}{2^n}$$

Servaes
  • 63,261
  • 7
  • 75
  • 163
  • I figured that eventually we will get $k!$ in the numerator, I didn't really know how to put it formally though. (?) – Analysis Aug 09 '19 at 13:38
  • What do you mean by 'get $k!$' in the numerator? Of course the numerator is divisible by $k!$ because $\tbinom{n}{k}$ is an integer. – Servaes Aug 09 '19 at 13:40
  • So, since $k$ is fixed, consider $3!$. We know that as $n\to \infty$, we will have $3!$ in the numerator eventually ... – Analysis Aug 09 '19 at 13:43
  • That does not make any clearer to me what you mean by 'have $3!$' in the numerator. Either way, you cannot simply omit the factor $k!$ and put an equals sign. The two expressions are not equal. – Servaes Aug 09 '19 at 14:13