4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ $n \in \mathbb{N}$, so basis must be shown for $n = 1$, not $0$. $\endgroup$ Jan 4, 2015 at 9:41
  • $\begingroup$ 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... $\endgroup$
    – Hoot
    Jan 4, 2015 at 9:55

3 Answers 3

7
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ is my statement holds for $n=0$. $\endgroup$
    – Educ
    Jan 4, 2015 at 13:21
  • $\begingroup$ By convention in combinatorics $0^0=1$ to make the binomial expansion work, so I do not see a problem with your initial step. $\endgroup$
    – Henry
    Jan 4, 2015 at 13:24
  • $\begingroup$ so i have just to add what you wrote and my prove will be okay $\endgroup$
    – Educ
    Jan 4, 2015 at 13:24
  • $\begingroup$ My answer was designed to replace your inductive step $\endgroup$
    – Henry
    Jan 4, 2015 at 13:25
  • $\begingroup$ 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 ? $\endgroup$
    – Educ
    Jan 4, 2015 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.