# division problem

• Aug 20th 2010, 02:56 PM
james12
division problem
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
• Aug 20th 2010, 03:12 PM
Quote:

Originally Posted by james12
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

To select "a" items from "a+b" items, there are

$\displaystyle \displaystyle\frac{(a+b)!}{a!(a+b-a)!}$ ways to do it.

That's an integer.
• Aug 20th 2010, 03:18 PM
james12
Hi Archie Meade, thanks for your reply, but is there a way to show/prove it's an integer?? This question is from a problem set in divisibility. Sorry, should of probably included that in the question
• Aug 21st 2010, 04:08 AM
HallsofIvy
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)!}$.
• Aug 21st 2010, 08:20 PM
james12
Thanks for your reply, I may see what I can find with the induction path, cheers =)
• Aug 22nd 2010, 01:49 AM
Unbeatable0
See here
• Aug 24th 2010, 05:02 PM
Quote:

Originally Posted by james12
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 number theory but hitting a few walls..

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.