I am working through a book: http://www.amazon.com/Discrete-Combinatorial-Mathematics-Applied-Introduction/dp/0201199122 .
Please note i am new to discrete math.
I have come past an example of Combinatorial proof of the below...and i feel i do not grasp it completely. Please do assist...i have attached a pic of the proof:
I feel i don't quite get how n!/2^k can always be an integer. As in this proof i do not see how n! will always be greater than 2^k(if 2^k is greater than n!...then it would be a rational number not an integer...correct? How would i prove that n! will always be greater than 2^k). I do see how it can always be divided by 2 because of the definition of factorials: n! = (n)(n-1)(n-2)x...x(2)(1)(1) where 2!=2, 1!=1 and 0!=1. so always someNumber x 2 at the end...therefore even and therefore divisible by 2.
This is the beginning of the book and im already getting stuck.
It's because $n!=(2k)!=(2k)\times(2k-1)\times(2k-2)\times\cdots\times2\times1$. How many even numbers are there in this product? There are $k$ even numbers. From each one of them you get a factor $2$.