proof $k!j!\leq(j+k)!$ by induction

Question

how do I prove that $k!j!\leq(j+k)!$

I have tried to use induction but didn't succeed.

any other ideas on how to prove it?

in witch case $k!j!=(j+k)!$ ?

Answer 1

HINT: Both $k!j!$ and $(j+k)!$ are products of $k+j$ factors. Write out the factors and compare them:

$$k!j!=1\cdot2\cdot3\cdot\ldots\cdot k\cdot \underbrace{1\cdot 2\cdot 3\ldots\ldots j}\;,$$

and

$$(k+j)!=1\cdot 2\cdot 3\cdot\ldots\cdot k\cdot\underbrace{(k+1)\cdot(k+2)\cdot(k+3)\cdot\ldots\cdot(k+j)}\;$$

compare the parts with the underbraces.

Or look at the fraction $\frac{k!j!}{(k+j)!}$ after writing out the factors as I did above. In this way you can avoid induction completely.

Answer 2

Induction doesn't seem like the easiest approach. Note that $j!k!$ is a product of $j+k$ integers, as is $(j+k)!$. Now simply compare these integers one by one.

Answer 3

$(j+k)! = 1*2*3........*(j+k) =$

$[1*2*........*j]*[(j+1)*(j+2)*(j+3)*.....*(j+k)]$.

Now $j+1 > 1$ and $j+2> 2$ and $j+i> i$ and so on.

So $(j+1)(j+2)(j+3).....(j+k) > 1*2*3*....*k$.

And $[1*2*.......*j]*[(j+1)*(j+2)*(j+3)*.....*(j+k)]> $

$[1*2*....*j]*[1*2*3*....*k]=$

$j!k!$.

.....

To do it by induction:

Claim: For any $k\in \mathbb N$, $j!k! < (j+k)!$ for all $j\in \mathbb N$.

Base case: $k = 0$.

$k! = 0! = 1$ and $j!k! = j!0! = j!*1 = j!$. While $(j+k) = j+0 = j$ so $(j+k)! = j!$. So $j!k! = (j+k)! = j!$.

Inductive step: Assume $j!k! \le (j+k)!$.

Then $0 < k+1 \le j+k + 1$. Then $j!k!(k+1) \le (j+k)!(k+1) \le (j+k)!(j+ k+1)$.

So $j!(k+1)! = j!k!(k+1)\le (j+k)!(j+k+1) = (j+k+1)!$.

Done.

Answer 4

Another approach is to observe that for $0 \le j,k \in \mathbb N$ the binomial coefficient, i.e. the number of ways in which you can choose a j-tuple from a (k+j)-tuple, which is:

$$\binom{j+k}{j} = \frac{(j+k)!}{j!k!}$$

is always a positive integer, so you can deduce that $(k+j)!$ is a multiple of $j!k!$, which implies that $j!k! \le(j+k)!$ .

Answer 5

noting that: $$^{j+k}C_k=\frac{(j+k)!}{j!k!}$$ Now think about what this represents, if we have $(j+k)$ items how many different combinations can be make a group of $k$, this must be greater than or equal to $1$ since we are choosing from a larger group or the same size group, therefore: $$\frac{(j+k)!}{j!k!}\ge1$$ $$(j+k)!\ge j!k!$$