True or False:
The following expression is an integer:
i = 1 ∏ n ( 4 − i 2 )
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
@Chris Lewis Thank you for sharing your solution.
Which contest problem is this?
i = 1 ∏ n ( 4 − i 2 ) = 2 n i = 1 ∏ n i 2 i − 1 = n ! 2 n ( 2 n − 1 ) ! ! = 2 n n ! ⋅ n ! 2 n ( 2 n ) ! = ( n ! ) 2 ( 2 n ) ! = ( n 2 n )
Note that a binomial coefficient ( k n ) is always an integer. True , the expression is an integer.
@Chew-Seong Cheong Thank you Sir for sharing your solution.
This is not a proof! I computed the values out to n = 1 0 0 0 0 . All values were integers. Therefore, I guessed answer as true.
So I guess, you probably used a loop in a software to compute that amount of numbers.
Table ( If [ ∏ i = 1 n ( 4 − i 2 ) ∈ Z , Nothing , n ] , { n , 0 , 1 0 0 0 0 } )
That is a single line of Wolfram Mathematica ( not Wolfram/Alpha) code. That expression requests a table (list) of the values of n which do not produce an integer in the product expression for a given n . The table is effective a loop over the values of n from 1 to 10000. I examined the expressions generated symbolically and could see the effects of counter-acting factorials. I did not see a way to prove that it was true to n → ∞ . For n = 1 0 0 0 0 , the result is a 6019 digit integer. For n = 1 0 0 0 0 0 , the result is a 60204 digit integer. For n = 1 0 0 0 0 0 0 , the result is a 602057 digit integer. I still am not claiming that that is a proof.
Added May 30, 2019: 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 2704156
I had the above sequence at hand when I first posted. Then, read the following comments to this explanation.
Log in to reply
Just a thought - clearly, a key step in my solution process was recognising the particular integers that were generated by this function. Once I realised they were central binomial coefficients, it gave me something concrete to try and prove.
Obviously, if the sequence isn't one you recognise, that doesn't help much. But what does help is plugging the first few terms into the OEIS search tool; in this case it would certainly put you on the right track. This isn't guaranteed to work, of course, but I often find it helpful.
Log in to reply
The counter-acting factorials should have been a major clue indicating binomial coefficients. Even though binomial coefficients were the start of my programming career in October 1964, they do not come immediately to mind. A previous comment of yours, in your solution above clued me to find a way to search for integer sequences ( Duh! ). That lead me directly to https://oeis.org/ and its search box. The resultant page would have given me the clue to a proof. Thank you!
@Randolph Herber Thank you for sharing it. We all learn from each other in some way or another.
You're welcome.
Problem Loading...
Note Loading...
Set Loading...
Let P n = ∏ i = 1 n ( 4 − i 2 ) .
Calculating the first few values, we get 2 , 6 , 2 0 , 7 0 , … . We recognise these are integers, and we might recognise them as the entries of the central "column" of Pascal's triangle. In fact, we have P n = ( n 2 n ) , which we can prove by induction:
Assume P n = ( n 2 n ) (we've already seen this is true up to n = 4 ). We have P n + 1 = ( 4 − n + 1 2 ) ( n 2 n )
Expanding, this is P n + 1 = 2 n + 1 2 n + 1 ⋅ n ! 2 ( 2 n ) ! = 2 n + 1 2 n + 1 ⋅ 2 n + 2 2 n + 2 ⋅ n ! 2 ( 2 n ) ! = n ! 2 ⋅ ( n + 1 ) 2 ( 2 n ) ! ⋅ ( 2 n + 1 ) ⋅ ( 2 n + 2 ) = ( n + 1 ) ! 2 ( 2 n + 2 ) ! = ( n + 1 2 n + 2 ) .
So, by induction, P n = ( n 2 n ) for all n , and this is certainly an integer.