A Contest Problem lll

True or False:

The following expression is an integer:

i = 1 n ( 4 2 i ) \large \prod_{i = 1}^{n} \left(4 - \frac {2}{i}\right)

True False

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.

3 solutions

Chris Lewis
May 29, 2019

Let P n = i = 1 n ( 4 2 i ) P_n=\prod_{i=1}^n \left( 4-\frac{2}{i} \right) .

Calculating the first few values, we get 2 , 6 , 20 , 70 , 2,6,20,70,\ldots . 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 = ( 2 n n ) P_n={2n\choose n} , which we can prove by induction:

Assume P n = ( 2 n n ) P_n={2n\choose n} (we've already seen this is true up to n = 4 n=4 ). We have P n + 1 = ( 4 2 n + 1 ) ( 2 n n ) P_{n+1}=\left( 4-\frac{2}{n+1} \right){2n\choose n}

Expanding, this is P n + 1 = 2 2 n + 1 n + 1 ( 2 n ) ! n ! 2 = 2 2 n + 1 n + 1 2 n + 2 2 n + 2 ( 2 n ) ! n ! 2 = ( 2 n ) ! ( 2 n + 1 ) ( 2 n + 2 ) n ! 2 ( n + 1 ) 2 = ( 2 n + 2 ) ! ( n + 1 ) ! 2 = ( 2 n + 2 n + 1 ) P_{n+1}=2\frac{2n+1}{n+1} \cdot \frac{(2n)!}{n!^2}=2\frac{2n+1}{n+1} \cdot \frac{2n+2}{2n+2}\cdot \frac{(2n)!}{n!^2}=\frac{(2n)! \cdot (2n+1)\cdot (2n+2)}{n!^2 \cdot (n+1)^2} = \frac{(2n+2)!}{(n+1)!^2}={2n+2 \choose n+1} .

So, by induction, P n = ( 2 n n ) P_n={2n\choose n} for all n n , and this is certainly an integer.

@Chris Lewis Thank you for sharing your solution.

Hana Wehbi - 2 years ago

Which contest problem is this?

Mr. India - 2 years ago

Log in to reply

AOP community problems.

Hana Wehbi - 2 years ago
Chew-Seong Cheong
May 30, 2019

i = 1 n ( 4 2 i ) = 2 n i = 1 n 2 i 1 i = 2 n ( 2 n 1 ) ! ! n ! = 2 n ( 2 n ) ! 2 n n ! n ! = ( 2 n ) ! ( n ! ) 2 = ( 2 n n ) \begin{aligned} \prod_{i=1}^n \left(4 - \frac 2i \right) = 2^n \prod_{i=1}^n \frac {2i-1}i = \frac {2^n\color{#3D99F6}(2n-1)!!}{n!} = \frac {2^n\color{#3D99F6}(2n)!}{{\color{#3D99F6}2^nn!} \cdot n!} = \frac {(2n)!}{(n!)^2} = \binom {2n}n \end{aligned}

Note that a binomial coefficient ( n k ) \dbinom nk is always an integer. True , the expression is an integer.

@Chew-Seong Cheong Thank you Sir for sharing your solution.

Hana Wehbi - 2 years ago

Log in to reply

You are welcome

Chew-Seong Cheong - 2 years ago

This is not a proof! I computed the values out to n = 10000 n=10000 . 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.

Hana Wehbi - 2 years ago

Table ( If [ i = 1 n ( 4 2 i ) Z , Nothing , n ] , { n , 0 , 10000 } ) \text{Table}\left(\text{If}\left[\prod _{i=1}^n \left(4-\frac{2}{i}\right)\in \mathbb{Z},\text{Nothing},n\right],\{n,0,10000\}\right)

That is a single line of Wolfram Mathematica ( not Wolfram/Alpha) code. That expression requests a table (list) of the values of n n which do not produce an integer in the product expression for a given n n . The table is effective a loop over the values of n 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 n\to\infty . For n = 10000 n=10000 , the result is a 6019 digit integer. For n = 100000 n=100000 , the result is a 60204 digit integer. For n = 1000000 n=1000000 , 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.

Chris Lewis - 2 years ago

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.

Hana Wehbi - 2 years ago

You're welcome.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...