Results 1 to 7 of 7

Math Help - division problem

  1. #1
    Junior Member
    Joined
    Jul 2010
    Posts
    29

    division problem

    Hi can anyone give a detailed solution to this?

    If a and b are natural numbers, then (a+b)!/a!b! is an integer

    Trying to teach my self numbeer theory but hitting a few walls =p
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by james12 View Post
    Hi can anyone give a detailed solution to this?

    If a and b are natural numbers, then (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\frac{(a+b)!}{a!(a+b-a)!} ways to do it.

    That's an integer.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2010
    Posts
    29
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,977
    Thanks
    1121
    One way to do it is to note that \begin{pmatrix}n \\ k \end{pmatrix}= \frac{n!}{k!(n-k)!} is the coefficient of x^ky^{n-k} in the binomial (x+ y)^k. Since the coefficients of x and y are 1, all such coefficients are positive integers.

    And, of course, \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, \frac{(a+ b)!}{a!b!}= \frac{(a+ 1)!}{a!1!}= a+ 1, an integer.

    Assume true for given b and look at \frac{(a+ b+1)!}{a!(b+1)!}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2010
    Posts
    29
    Thanks for your reply, I may see what I can find with the induction path, cheers =)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2009
    Posts
    106
    See here
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by james12 View Post
    Hi, can anyone give a detailed solution to this?

    If a and b are natural numbers, then (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.

    \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\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 0!=1

    Or, we can simply work with the binomial exclusively.

    So, taking the multinomial coefficient...


    P(k)

    \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 \; x\; is an integer variable, that is, it can vary but takes on only positive integer values.

    To illustrate....

    \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\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.

    a_1+a_2+.....+a_n=k+1


    However, we utilise the fact that

    \left(a_1-1\right)+a_2+.....+a_n=k

    a_1+\left(a_2-1\right)+.....+a_n=k

    a_1+a_2+........+\left(a_n-1\right)=k

    Then...

    \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!}

    \text{\footnotesize\ We\ want\ to\ know\ if\;}y\text{\footnotesize\;\ is\ an\ integer.}

    \text{\footnotesize\ Divide\ both\ sides\ by\;\;\;} \left(a_1+a_2+......+a_n\right)\;\;\;\text{\footno  tesize\ and\ multiply\ both\ sides\ by\;\;\;}\ a_1

    \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

    \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}

    \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\ y=\sum_{j=1}^n\;\frac{a_j\,y}{a_1+a_2+......+a_n}


    \text{\footnotesize\ If\;}x\text{\footnotesize\;\ is an integer when\;}a_1+a_2+....+a_n=k,

    \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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Division Problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 29th 2010, 06:32 PM
  2. Division problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 5th 2009, 07:29 PM
  3. Division problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 28th 2009, 07:07 AM
  4. Division Problem
    Posted in the Algebra Forum
    Replies: 7
    Last Post: April 3rd 2008, 08:19 AM
  5. Division Problem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: January 19th 2007, 06:20 AM

Search Tags


/mathhelpforum @mathhelpforum