Hi can anyone give a detailed solution to this?
If a and b are natural numbers, then $\displaystyle (a+b)!/a!b!$ is an integer
Trying to teach my self numbeer theory but hitting a few walls =p
One way to do it is to note that $\displaystyle \begin{pmatrix}n \\ k \end{pmatrix}= \frac{n!}{k!(n-k)!}$ is the coefficient of $\displaystyle x^ky^{n-k}$ in the binomial $\displaystyle (x+ y)^k$. Since the coefficients of x and y are 1, all such coefficients are positive integers.
And, of course, $\displaystyle \frac{(a+ b)!}{a!b!}= \frac{(a+ b)!}{(a+b- b)!b!}= \frac{n!}{(n-k)!k!}= \begin{pmatrix}n \\ k\end{pmatrix}$ with n= a+ b and k= b.
If you don't like that, try proving it by induction on b with a fixed.
If b= 1, $\displaystyle \frac{(a+ b)!}{a!b!}= \frac{(a+ 1)!}{a!1!}= a+ 1$, an integer.
Assume true for given b and look at $\displaystyle \frac{(a+ b+1)!}{a!(b+1)!}$.
Hi James,
I'll try a "Proof By Induction" on this,
though it has not been as straightforward as the PBI proofs I've done up to now.
$\displaystyle \text{\footnotesize We\ know\ that\;\;\;} \displaystyle\frac{(a+b)!}{a!\,b!}\;\;\; \text{\footnotesize is\ a\ positive\ integer\ from\ our\ "counting"\ formula.}$
Aside from that, the following is an attempted proof using PBI.
$\displaystyle \displaystyle\text{\footnotesize We\ can\ take\ the\ general\ \bold{multinomial coefficient}}\;\;\; \frac{(a_1+a_2+.......+a_n)!}{a_1!\,a_2!\,........ \,a_n!}$
and prove it must be a positive integer for all of the terms being positive integers,
then deduce the binomial from that by setting all but 2 terms to zero,
since $\displaystyle 0!=1$
Or, we can simply work with the binomial exclusively.
So, taking the multinomial coefficient...
P(k)
$\displaystyle \displaystyle\frac{(a_1+a_2+.....+a_n)!}{a_1!\,a_2 !\,.........\,a_n!}=x\in\Bbb{N}\;\;\; \bold{whenever}\;\;\; a_1+a+a_2+...+a_n=k$
This means that the integers summing to k may be different sets of integers, but they do sum to k.
It also means that $\displaystyle \; x\;$ is an integer variable, that is, it can vary but takes on only positive integer values.
To illustrate....
$\displaystyle \displaystyle\frac{5!}{1!\,4!}=5,\;\;\text{while}\ ;\;\frac{5!}{2!\,3!}=10$
Therefore, the base case involves establishing this framework for initial values.
For example, suppose k=5 (though we would start with k=smallest practical value of interest)...
Then...
$\displaystyle \displaystyle\frac{5!}{1!\,4!}=5,\;\;\;\frac{5!}{2 !\,3!}=10,\;\;\;\frac{5!}{1!2!2!}=30$
for positive integers, and n=2 or 3.
P(k+1)
The set of integers sum to k+1.
$\displaystyle a_1+a_2+.....+a_n=k+1$
However, we utilise the fact that
$\displaystyle \left(a_1-1\right)+a_2+.....+a_n=k$
$\displaystyle a_1+\left(a_2-1\right)+.....+a_n=k$
$\displaystyle a_1+a_2+........+\left(a_n-1\right)=k$
Then...
$\displaystyle \displaystyle\frac{\left(a_1+a_2+......+a_n\right) !}{a_1!\,a_2!\,....\,a_n!}=y=\frac{(k+1)!}{a_1!\,a _2!\,....a_n!}$
$\displaystyle \text{\footnotesize\ We\ want\ to\ know\ if\;}y\text{\footnotesize\;\ is\ an\ integer.}$
$\displaystyle \text{\footnotesize\ Divide\ both\ sides\ by\;\;\;} \left(a_1+a_2+......+a_n\right)\;\;\;\text{\footno tesize\ and\ multiply\ both\ sides\ by\;\;\;}\ a_1 $
$\displaystyle \Rightarrow\displaystyle\frac{a_1\,y}{a_1+a_2+.... .+a_n}=\frac{\left[\left(a_1-1\right)+a_2+....+a_n\right]!}{\left(a_1-1\right)!\,a_2!\,....\,a_n!}=x_i,\text{\footnotesi ze\ \;one\ of\ the\ values\ of\;\;} x$
$\displaystyle \text{\footnotesize\ Similarly\ for\;\;\;}\displaystyle\frac{a_2\,y}{a_1+a_2+....+ a_n}\;,.......,\;\frac{a_n\,y}{a_1+a_2+....+a_n}$
$\displaystyle \text{\footnotesize\ Then,\ if\ we\ sum\ all\ of\ these,\ the\ result\ is\;\;}y,\text{\footnotesize\; hence\;\;}y\text{\footnotesize\;\;is\ the\ sum\ of\ integers,\ so\ it's\ an\ integer\ also.}$
$\displaystyle \displaystyle\ y=\sum_{j=1}^n\;\frac{a_j\,y}{a_1+a_2+......+a_n}$
$\displaystyle \text{\footnotesize\ If\;}x\text{\footnotesize\;\ is an integer when\;}a_1+a_2+....+a_n=k,$
$\displaystyle \text{\footnotesize\ then\;}y \text{\footnotesize\;\ is certainly an integer when\;}a_1+a_2+....+a_n=k+1$
Hence the inductive step is complete.