How would one go about proving that:
is always a natural number? That is, assuming and that and that ; what I mean by that is that and are both positive integers. Its a question in my textbook that I bought early to get ahead on fall classes, so I don't have any teachers to ask about this question; not till fall atleast. I'm not asking for a straight out proof, but preferably some direction as to where I would go, which direction I should go to prove this? A litttle guidence is all I need, please don't simply give me the full answer, if you don't mind. Thanks in advance
There's also the combinatorial proof. (The binomial coefficient is given as an "archetypal example" not far from the top of the page.) The formula(s) given for can be shown to equal either of the two equivalent quantities
1) the coefficient of the term in the polynomial expansion of the binomial power
2) the number of ways to choose k elements from a set of n elements. (The number of distinct k-subsets of {1, 2, ... , n}.)
Obviously both of these quantities are integers.
Another way is to use Legendre's formula, which states that ( is the set of prime numbers)
Thus for any prime we have:
So all what's left is to show that
so it follows that for all :
and therefore
If you are asking from the perspective of the Binomial Expansion,
then you can observe a pattern if you refrain from expressing the terms with indices...
"a" times "b" is expressed in both possible ways.
If the "a" values were labelled we could arrange them,
hence we have all possible selections of 2 "a"'s with a "b", 2 "b"'s with an "a",
the only possible selection of 3 "a"s, the only selection of 3 "b"'s.
For higher powers, the same pattern exists.
Since this pattern is the same as "choose k from n available",
the binomial coefficient may be calculated using
There are k! arrangements of a selection.
As shown above, the number of selections is a natural number,
which can be calculated by "unarranging" the arrangements.
The number of arrangements of k from n is n(n-1)(n-2)...(n-[k-1])
which is as k! has been "cut off" the tail.
The number of arrangements is k! times the number of selections.