wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> factorial problem
        
(Message started by: Deedlit on Jun 14^th, 2005, 1:26am)

Title: factorial problem
Post by Deedlit on Jun 14^th, 2005, 1:26am

Show that [n! / ((n+1)(n+2)) ] is even for nonnegative integers n. ( [] is the greatest integer function.)

Title: Re: factorial problem
Post by SWF on Jun 22^nd, 2005, 6:32pm

Simple calculation shows it to be true for n<5. It is convenient to continue in terms of n=2m and n=2m-1 for m>2.

When m>2, (2m)!/(2m+2) and (2m-1)!/(2m) are both integers and

(2m)!/(2m+2) - (2m-1)!/(2m) = (2m+1)*(2m-1)!*(m-1) / (2*m*(m+1))

As their difference is a multiple of 2m+1, both of these integers have the same remainder when divided by 2m+1 Also,

(2m)! - (2m)!/(2m+2) = (2m+1)*(2m)! / (2m+2),

and (2m)! must also have the same remainder when divided by 2m+1. In other words, for a given value of m>2, there are 4 integers A, B, C, and r with 0 <= r < 2m+1 and:

(2m)!/(2m+2) = A*(2m+1) + r
(2m-1)!/(2m) = B*(2m+1) + r
(2m)! = C*(2m+1) + r

When m>2, the left side of all three equalities is an even integer. As (2m)! is a multiple of 2m+1, unless 2m+1 is a prime, r is either zero or 2m+1 is prime. By Wilson's Theorem, when 2m+1 is prime, r = 2m. Either way, r is an even number, and since (2m+1) is odd, A, B, and C are all even. B and A are the integer parts of dividing the above by 2m+1. i.e. the integer portions of

(2m-1)!/(2m)/(2m+1) and (2m)!/(2m+1)/(2m+2)

are even, which takes care of odd and even values of n.

Title: Re: factorial problem
Post by Barukh on Jun 23^rd, 2005, 10:46am

As always, SWF provides an excellent solution! The idea to consider different quotients for even and odd numbers is so nice... :D

Title: Re: factorial problem
Post by SWF on Jun 27^th, 2005, 8:45pm

Thank you, Barukh. The even/odd thing was something I noticed when numerically trying n=1 through 10, then tried to prove it. I wonder if that is the intended way of showing this, or if there is an easier way- where is Deedlit?

Did anyone even try this problem? It sat around for a while with 0 comments, which is rare.

Title: Re: factorial problem
Post by Barukh on Jun 28^th, 2005, 2:29am

on 06/27/05 at 20:45:25, SWF wrote:

Did anyone even try this problem? It sat around for a while with 0 comments, which is rare.

And what about this (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1118011634)? I have an idea, but it's based on a conjecture I cannot prove.

Title: Re: factorial problem
Post by TenaliRaman on Jul 2^nd, 2005, 1:41am

Thats a beautiful proof SWF! So simple, yet so neat!! :o

-- AI

Title: Re: factorial problem
Post by Deedlit on Aug 2^nd, 2005, 8:52pm

I agree, very nice!