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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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