一個整除問題 一個整除問題

Use MI
when n=0, the statement is obviously true
when n=1, the statement is also obviously true

Assume that when n=k, the statement is true

i.e. k! is divisible by r!(k-r)! 0<=r<=k

when n=k+1

(k+1)!
=k!(k+1)

Want to prove that it is divisible by r!(k-r+1)!=r!(k-r)!(k+1) 0<=r<=k+1

Since k! is divisible by r!(k-r)! 0<=r<=k

For 0<=r<=k, we can see that (k+1)! is divisible by r!(k-r+1)!

If r=k+1

Then r!(k-r+1)!=(k+1)! which is also divide (k+1)!

So when n=k+1, the statement is true

By MI for all non-negative integers n, n! is divisible by r!(n-r)! 0<=r<=n