trying to show that n choose k less than 2^n

Question

I am trying to show that:

$\binom{n}{k} \leq 2^n$

For all positive integers n and integers k with $0 \leq k \leq n$.

Can anyone give me a hand?

Answer 1

HINT:

$$2^n=(1+1)^n=\sum_{0\le k\le n}\binom nk$$

Answer 2

Another thought: If you have a selection of $k$ items from a list of $n$, you can make a corresponding $n$-digit binary number, with a $1$ in the $k$ spots you selected. For instance, choosing $k=3$ numbers from the set ${1, 2, 3, 4, 5, 6, 7}$, you might select 2, 3, and 6. That would correspond to the binary number

0110010

(the 2nd, 3rd, and 6th bits are ones).

The set of ALL $n$-bit binary numbers has $2^n$ elements. The set of numbers with exactly $k$ bits being "1"s is clearly a proper subset. Hence the number of ways of choosing $k$ items from $n$ is smaller than $2^n$.

(This is a restatement of @lab bhattacharjee's answer -- the $n$ terms in his sum correspond to the counts of how many n-bit binary numbers have 0 1's, 1 1's, 2 1's, etc.)

Answer 3

Hey Thank you everyone for your help!

From the binomal theorem we have:

$(x+y)^n = \sum_{k=0}^n \binom{n}{k}x^k y^{n-k}$

as suggested by lab bhattacharjee we use $x=y=1$ and get

$(1+1)^n = 2^n = \sum_{k=0}^n \binom{n}{k} \geq \binom{n}{k}$

which shows directly that

$\binom{n}{k} \leq 2^n$