# prove $\binom{n}{k}\frac{1}{n^k}\leq\frac{1}{k!}$

i am learning maths so fast here in MSE, thank you guys so much for being here to help us!

so now, my next step towards proficiency: :).

i am trying to prove that $\binom{n}{k}\frac{1}{n^k}\leq\frac{1}{k!}$ for $n\geq1$ and for all $k\in\Bbb{N}$. My first problem is that i never tried to prove a statement with induction where i have two dependencies. here $n$ and $k$.

induction base: $n=1$ and $k=1$. $\binom{1}{1}\frac{1}{1^1}\leq\frac{1}{1!}$ which is okay.
inductive hypothesis: for $n\geq1$ and for all $$k\in\Bbb{N},~~\binom{n}{k}\frac{1}{n^k}\leq\frac{1}{k!}$$ 1)first induction step: $$n\rightarrow n+1~~ \text{and}~~ k,\binom{n+1}{k}\frac{1}{(n+1)^{k}}\leq\frac{1}{(k)!}$$ 2)second induction step: $n$ and $$k\rightarrow k+1,~~\binom{n}{k+1}\frac{1}{(n)^{k+1}}\leq\frac{1}{(k+1)!}$$

1)$$\binom{n+1}{k}\frac{1}{(n+1)^{k}}=\Bigg(\binom{n}{k}+\binom{n}{k-1}\Bigg)\frac{1}{(n+1)^{k}} =\\ \binom{n}{k}\frac{1}{(n+1)^{k}} + \binom{n}{k-1}\frac{1}{(n+1)^{k}} \leq \frac{1}{(k)!}$$

2) Help.

I am having hard time to prove further in calculations, can you pls show me further? is 1) right? i am not sure

-
For two-point induction, you first prove the basis case for $n=k=1$, and then you have two inductive steps, first proving that if the hypothesis holds for $n=x$ and $k=y$ then $\implies$ the hypothesis holds for $n=x+1$ and $k=y$ and then show that if the hypothesis holds for $k=x$ and $n=y$ then $\implies$ that it holds for $k=x+1$ and $n=y$. – Shaktal Dec 23 '12 at 20:43
I assume you only want yes or no. It is insufficient, $k$ and $n$ are independent. – André Nicolas Dec 23 '12 at 20:44
For a non-induction, combinatorial proof: ${n\choose k}k!$ is the number of ordered lists of length $k$ with entries taken from a set of size $n$ without repetition allowed, whereas $n^k$ is the number of ordered lists of length $k$ with entries taken from a set of size $n$ with repetition allowed. The lists in the former category are in the latter category but not necessarily vice-versa, which establishes the inequality by rewriting as so: ${n\choose k}k!\le n^k\iff {n\choose k}\frac{1}{n^k}\le k!$. – anon Dec 24 '12 at 1:19
great @anon i forgot that, nice remembering und explanation! thanks a lot – doniyor Dec 24 '12 at 6:47

In general, for inductions involving two independent natural numbers (here, $n$ and $k$, with $n, k \ge 1$), the strategy is as follows:

• You first prove the basis case for $n=k=1$, which you have done.

• Then you state an inductive hypothesis that the property holds for $n = a$ and $k = b$.

• Then you need two inductive steps, and for each you assume the inductive hypothesis to be true, i.e. you'll want to use the inductive hypothesis to

• First, prove the hypothesis also holds for $n=a+1$ and $k = b$; and
• Then, prove that the hypothesis also holds for $n=a, k = b+1$.
-
Oh, okay, that is what i was looking for, great thanks alot – doniyor Dec 23 '12 at 20:51
Good...you're on your way then! – amWhy Dec 23 '12 at 20:52
can you pls check my edited question? – doniyor Dec 23 '12 at 21:24
Yes, the statement immediately following each inductive step is what you want to prove: can you show more justification? – amWhy Dec 23 '12 at 21:27

Note that $k! \dbinom{n}k = \dfrac{n!}{(n-k)!} = n(n-1)(n-2) \cdots (n-k+1)$. Hence, you want to show that $$n(n-1)(n-2) \cdots (n-k+1) \leq n^k$$ Can you now show this?

-