Proving It Is The Fun Part!

Algebra Level 5

1 ( x + 1 ) ( x + 2 ) ⋯ ( x + 999 ) \dfrac1{(x+1)(x+2)\cdots(x+999) }

The partial fraction decomposition of the expression above can be expressed as ∑ m = 1 999 a m x + m \displaystyle \sum_{m=1}^{999} \dfrac {a_m}{x+m} for some a 1 , a 2 , … , a 999 a_1, a_2, \ldots , a_{999} .

If max ⁡ { ∣ a 1 ∣ , ∣ a 2 ∣ , … , ∣ a 999 ∣ } = 1 ( Q ! ) 2 \max \{|a_1|, |a_2|, \ldots, |a_{999}|\} = \dfrac{1}{(Q!)^2} , find Q Q .

Notations :

  • ∣ ⋅ ∣ | \cdot | denotes the absolute value function .
  • ! ! denotes the factorial notation. For example, 8 ! = 1 × 2 × 3 × ⋯ × 8 8! = 1\times2\times3\times\cdots\times8 .


The answer is 499.

View wiki
Pi Han Goh by Pi Han Goh , 30, Malaysia

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.

2 solutions

Pi Han Goh
Aug 8, 2016

Relevant wiki: Partial Fractions - Cover Up Rule

Naturally, the first step is to find the closed form of a j a_j where j = 1 , 2 , … , 999 j=1,2,\ldots , 999 .

By cover up rule , the value of 1 a j \dfrac1{a_j} can be expressed as

( − j + 1 ) ( − j + 2 ) ⋯ ( − j + j − 2 ) ( − j + j − 1 ) ⏟ = ± ( j − 1 ) ! ( x + j ) 1 ( − j + j + 1 ) ( − j + j + 2 ) ⋯ ( − j + 999 ) ⏟ = ( 999 − j ) ! = ± ( j − 1 ) ! ( 999 − j ) ! \large \underbrace{(-j+1)(-j+2)\cdots (-j+j-2)(-j+j-1)}_{= \pm (j-1)!} \; \cancelto1{(x+j)} \; \underbrace{(-j+j+1)(-j+j+2) \cdots (-j+999) }_{=(999-j)!} \\ = \pm (j-1)! \; (999-j)!

Hence, ∣ a j ∣ = ∣ 1 ( j − 1 ) ! ( 999 − j ) ! ∣ ⇔ ∣ a j ∣ ⋅ 998 ! = ( ( j − 1 ) + ( 999 − j ) ) ! ( j − 1 ) ! ( 999 − j ) ! = ( 998 j − 1 ) | a_j | = \left | \dfrac1{(j-1)! (999-j)!} \right | \Leftrightarrow | a_j | \cdot 998! = \dfrac{ ( (j-1) + (999-j) )! }{ (j-1)! (999-j)!} = \dbinom{998}{j-1} .

This leaves us with finding the maximum (integer) value of ( 998 j − 1 ) \dbinom{998}{j-1} .

By looking at the Pascal's triangle , the largest value of ( 2 N A ) \dbinom{ 2N}{A} for constant N > 0 N> 0 occurs when A = N A = N . (The proof is left as an exercise for the readers).

Thus, max ⁡ 1 ≤ j ≤ 998 ( 998 j − 1 ) = ( 998 998 / 2 ) ⇒ j − 1 = 998 2 = 499 ⇒ j = 500 {\max}_{{1\leq j \leq 998}} \dbinom{998}{j-1} = \dbinom{998}{998/2} \Rightarrow j - 1 = \dfrac{998}2 = 499\Rightarrow j = 500 .

And so max ⁡ { ∣ a 1 ∣ , ∣ a 2 ∣ , … , ∣ a 999 ∣ } = 1 ( 500 − 1 ) ! ( 999 − 500 ) ! = 1 ( 499 ! ) 2 \max \{|a_1|, |a_2|, \ldots, |a_{999}|\} = \dfrac1{(500-1)! (999- 500)!} = \dfrac1{(499!)^2 } . Hence, Q = 499 Q = \boxed{499} .

Footnote : Can you generalize this?

3 Helpful 0 Interesting 0 Brilliant 0 Confused

Moderator note:

The cover-up rule is an underutilized technique for partial fraction decomposition. Note that the solution manages to explain how to find the value of ALL the values of a j a_j in one single step!

Since the coefficient 1 a j \dfrac1{a_j} is in the form of a ! b ! a! b! , where a + b a + b is a constant, it is a natural to consider rewriting the value of 1 a j \dfrac1{a_j} in terms of the binomial coefficient ( a + b a ) = ( a + b b ) = ( a + b ) ! a ! b ! \dbinom {a+b}a = \dbinom{a+b}b = \dfrac{(a+b)!}{a! b!} .

OH! So this is called the cover-up rule. My teacher used to call it the "takip" method (literally covering method) when he taught us this.

Manuel Kahayon - 4 years, 10 months ago

Log in to reply

It's an underrated technique!!

Pi Han Goh - 4 years, 10 months ago

Log in to reply

Agree. I only saw it for two times in my entire math career: Once from my teacher, twice here.

Manuel Kahayon - 4 years, 10 months ago
Anubhav Tyagi
Aug 17, 2016

GREAT PROBLEM BUT I HAD SOLVED SIMILAR PROBLEMS EARLIER SO NOT A DIFFICULT ONE

0 Helpful 0 Interesting 0 Brilliant 0 Confused

OKAY! THANK YOU! WHY ARE YOU TYPING IN CAPS LOCK????!?!?!?!?!?!?!?!

Pi Han Goh - 4 years, 10 months ago

Ahh... SORRY Buddy

Anubhav Tyagi - 4 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...