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