# Show that ${n \choose k}\leq n^k$

Let $$n$$ et $$k\in \mathbb{N}$$ such that : $$k\leq n$$

Show that :$${n \choose k}\leq n^{k}$$

My thoughts:

note that for all $$\ k\leq n$$ :

$${n \choose k}=\frac{n!}{k!(n-k)!}$$

To prove that the following statement, which we will call $$P(n)$$, holds for all natural numbers n:$${n \choose k}\leq n^{k}$$

so my proof that P(n) is true for each natural number n proceeds as follows:

Basis: Show that the statement holds for $$n=0$$.

P($$0$$) amounts to the statement: $${0 \choose 0}=\frac{0!}{0!(0-0)!}\leq 0^{0},\quad (k\leq 0 \implies k=0)$$ $$0\leq 0$$ the statement is true for $$n=0$$. Thus it has been shown that P($$0$$) holds.

Inductive step: Show that if P($$k$$) holds, then also P($${k+1}$$) holds. This can be done as follows.

Assume P($$n$$) holds. It must then be shown that P($$n+1$$) holds, that is: $${{n+1} \choose k}\leq {(n+1)}^{k}$$

note that $$\binom{n+1}{k+1} = \frac{(n+1)}{(k+1)}\binom n k$$

$$\binom{n+1}{k} = \frac{(n+1)}{(k)}\binom n {k-1}$$

Using the induction hypothesis that P($$n$$) holds, the last expression can be rewritten to: $$\binom{n+1}{k} = \frac{(n+1)}{(k)}\binom n {k-1}\leq \frac{(n+1)}{(k)}{(n)}^{k-1}$$

i'm stuch here thereby i can't showing that indeed P($$n+1$$) holds.

• Am i right and is there others ways to prove it

Edit:

Basis: Show that the statement holds for $$n=0$$.

P($$0$$) amounts to the statement: $${0 \choose 0}=\frac{0!}{0!(0-0)!}\leq 0^{0},\quad (k\leq 0 \implies k=0)$$ $$0\leq 0$$ the statement is true for $$n=0$$. Thus it has been shown that P($$0$$) holds.

Inductive step: Show that if P($$k$$) holds, then also P($${k+1}$$) holds. This can be done as follows.

Assume P($$n$$) holds. It must then be shown that P($$n+1$$) holds, that is: $${{n+1} \choose k}\leq {(n+1)}^{k}$$

note that $$\displaystyle{n+1 \choose k}={n \choose k-1}+{n \choose k}$$ Using the induction hypothesis that P($$n$$) holds, the last expression can be rewritten to:

$$\displaystyle{n+1 \choose k}\le n^{k-1}+n^k=(1+n)n^{k-1} \le (n+1)^k$$ though for completeness you might add that $${n+1 \choose 0}=1\le (n+1)^0$$ and $${n+1 \choose n+1}=1\le (n+1)^{n+1}$$.

because the main part does not quite work for $$\displaystyle {n+1 \choose 0}={n \choose -1}+{n \choose 0}$$ or for $$\displaystyle{n+1 \choose n+1}={n \choose n}+{n \choose n+1}$$

the inductive hypothesis does not cover either $$\displaystyle{n \choose -1}$$ or $$\displaystyle{n \choose n+1}.$$

Is my reasoning correct

• $n \in \mathbb{N}$, so basis must be shown for $n = 1$, not $0$. Jan 4, 2015 at 9:41
• I wonder how hard it would be to turn the idea of "both sides are the number of ways to choose $k$ objects from $n$, but the right hand side keeps track of order" into a proof. To be honest, I've accepted reasoning like this when teaching combinatorics but standards vary. Maybe write, with $J = \{1, \dots, n\}$, the obvious map $J^n \to (\text{subsets of$J$of size$k$})$, argue that it's surjective. Of course, then one ought to justify that the two sides have the right orders, that a surjection between finite sets induces an inequality...
– Hoot
Jan 4, 2015 at 9:55

Another idea: $$\binom{n}{k} = \frac{n(n-1)(n-2) \cdots (n-k+1)}{k!} \leq n(n-1)(n-2) \cdots (n-k+1) \leq n^k.$$

• but you didn't told me if i am right or nope or even we can prove it by induction
– Educ
Jan 4, 2015 at 12:28

$n \choose k$ counts the number of subsets of size $k$ from a set of $n$ elements. $n^k$ counts the number of ordered strings of length $k$ from a set of $n$ elements. Clearly, there are more ordered strings of length $k$ than there are unordered subsets of the size $k$, and thus the inequality holds.

It can be shown by induction.

From Pascal's triangle you have $\displaystyle{n+1 \choose k}={n \choose k-1}+{n \choose k}$ and so applying your inductive hypothesis $$\displaystyle{n+1 \choose k}\le n^{k-1}+n^k=(1+n)n^{k-1} \le (n+1)^k$$ though for completeness you might add that ${n+1 \choose 0}=1\le (n+1)^0$ and ${n+1 \choose n+1}=1\le (n+1)^{n+1}$.

• is my statement holds for $n=0$.
– Educ
Jan 4, 2015 at 13:21
• By convention in combinatorics $0^0=1$ to make the binomial expansion work, so I do not see a problem with your initial step. Jan 4, 2015 at 13:24
• so i have just to add what you wrote and my prove will be okay
– Educ
Jan 4, 2015 at 13:24
• My answer was designed to replace your inductive step Jan 4, 2015 at 13:25
• but i can't see why we ve to add that : ${n+1 \choose 0}=1\le (n+1)^0$ and ${n+1 \choose n+1}=1\le (n+1)^{n+1}$. i think $\displaystyle{n+1 \choose k}\le (n+1)^k$ holds for $k\leq n$ am i right ?
– Educ
Jan 4, 2015 at 13:31