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

Solution 1:

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?

Solution 2:

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