Why $n^{\underline k} \le n^k$?

Question

As in the title,

I cannot prove why $n^{\underline k} \le n^k$

$n^{\underline k}$ is denoted as falling factorial. That is $n^{\underline k} = n \times (n-1) \times \cdots \times (n-k+1)$

Can anyone help me out this, please?

Answer 1

There are $k$ terms in the product $n \times (n-1) \times \dots \times (n - k +1)$. Each one of them is positive and inferior to $n$. So the product is inferior to $n^k$.

One way of seeing there are $k$ terms is remarking that $n - (n-k+1) + 1 = k$.

Answer 2

If there are $n$ objects and we are to pick $k$ objects to assign to a list of length $k$,

• if we pick with replacement, there are $n^k$ different lists of length $k$;
• if we pick without replacement, there are $n^{\underline k}$ different lists of length $k$.

And ways to pick with replacement include every way to pick without replacement, so

$$n^{\underline k} \le n^k$$