My Dad's Favorite

Algebra Level 5

f ( x ) = x 150 + x 149 + x 148 + + x + 1 \large f(x) = x^{150} + x^{149} + x^{148} + \cdots + x +1

Let x 1 x_{1} , x 2 x_{2} \ldots x 150 x_{150} be the roots of the equation f ( x ) = 0 f(x) = 0 .

Then find the value of

1 i < j 150 1 ( 1 x i ) ( 1 x j ) \ \sum_{1\leq i < j \leq 150} \dfrac{1}{(1-x_{i})(1-x_{j})}


This is my original problem.
Try this problem 150 Followers Problem .


The answer is 3725.

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.

4 solutions

We are going to find a polynomial with roots t = 1 1 x t=\dfrac{1}{1-x} , so solving for x x :

x = t 1 t x=\dfrac{t-1}{t}

The equation is x 151 1 x 1 = 0 \dfrac{x^{151}-1}{x-1}=0 for x 1 x\neq 1 , so t 0 t\neq 0 :

( t 1 t ) 151 1 t 1 t 1 = 0 \dfrac{\left(\dfrac{t-1}{t}\right)^{151}-1}{\dfrac{t-1}{t}-1}=0

t 151 ( t 1 ) 151 = 0 t^{151}-(t-1)^{151}=0

If we expand it using the binomial theorem, we get:

( 151 1 ) t 150 ( 151 2 ) t 149 + ( 151 3 ) t 148 + = 0 \dbinom{151}{1}t^{150}-\dbinom{151}{2}t^{149}+\dbinom{151}{3}t^{148}+\cdots=0

By Vieta's formulas, the sum we want is coefficient of t 148 coefficient of t 150 \dfrac{\text{coefficient of }t^{148}}{\text{coefficient of }t^{150}} :

( 151 3 ) ( 151 1 ) = 151 × 150 × 149 2 × 3 151 \dfrac{\dbinom{151}{3}}{\dbinom{151}{1}}=\dfrac{\dfrac{151\times150\times149}{2\times 3}}{151}

150 × 149 6 = 3725 \dfrac{150 \times 149}{6}=\boxed{3725}

In general, for the equation x n + x n 1 + + x + 1 = 0 x^n+x^{n-1}+\cdots+x+1=0 , the sum is n ( n 1 ) 6 \dfrac{n(n-1)}{6}

Doesn't cyclotomic polynomials trivialize this problem?

Richard Ritz - 5 years, 9 months ago

Log in to reply

Can you elaborate on this?

Pi Han Goh - 5 years, 9 months ago

Log in to reply

See here: http://en.wikipedia.org/wiki/Root of unity#cyclotomicpolynomials

Richard Ritz - 5 years, 9 months ago

Log in to reply

@Richard Ritz can you show the working which trivialize the problem?

Pi Han Goh - 5 years, 9 months ago

But how did you arrive at (x^151 - 1)/( x-1)= 0?

Vinay Seth - 5 years, 9 months ago

Log in to reply

Let S = x 150 + x 149 + + x + 1 S=x^{150}+x^{149}+\cdots+x+1 , then multiply by x x : S x = x 151 + x 150 + + x 2 + x Sx=x^{151}+x^{150}+\cdots+x^2+x . Subtract these two expressions, solve for S S and you get the result. This is the sum of a geometric progression.

Alan Enrique Ontiveros Salazar - 5 years, 9 months ago

Log in to reply

Hey thanks! Yes- I had studied GP back in school but had completely forgotten about this! (Part of the reason I decided to join this online community) Thanks a ton, mate :)

Vinay Seth - 5 years, 9 months ago
Surya Prakash
Aug 31, 2015

Since x 1 x_{1} , x 2 x_{2} , x 3 x_{3} \ldots x 150 x_{150} are the roots f ( x ) = 0 f(x)=0 . It implies that f ( x ) = ( x x 1 ) ( x x 2 ) ( x x 150 ) f(x) = (x-x_{1})(x-x_{2})\ldots (x-x_{150}) .

It's easily observable that by differentiating f ( x ) f(x) twice w.r.t x x . We get,

f ( x ) = 2 f ( x ) ( 1 i < j 150 1 ( x x i ) ( x x j ) ) f''(x) = 2f(x) \left(\sum_{1 \leq i < j \leq 150} \dfrac{1}{(x-x_{i})(x-x_{j})} \right)

So, 1 i < j 150 1 ( 1 x i ) ( 1 x j ) = f ( 1 ) 2 f ( 1 ) \sum_{1 \leq i < j \leq 150} \dfrac{1}{(1-x_{i})(1-x_{j})} = \dfrac{f''(1)}{2f(1)}

But, f ( 1 ) = 1 + 1 + + 1 151 number of 1’s = 151 f(1) = \underbrace {1+1+\ldots + 1} _{151 \text{number of 1's}} = 151

And f ( x ) = 150 × 149 x 148 + 149 × 148 x 147 + + 2 × 1 f''(x) = 150\times 149 x^{148} +149 \times 148 x^{147} + \ldots + 2 \times 1 . So, f ( 1 ) = 150 × 149 + 149 × 148 + 2 × 1 = 1124950 f''(1) = 150 \times 149 + 149 \times 148 \ldots + 2 \times 1 = 1124950

So, therefore

1 i < j 150 1 ( 1 x i ) ( 1 x j ) = 1124950 2 × 151 = 3725 \sum_{1 \leq i < j \leq 150} \dfrac{1}{(1-x_{i})(1-x_{j})} = \dfrac{1124950}{2 \times 151} =\boxed{3725}

Vieta is all you need.

Billy Sugiarto - 5 years, 9 months ago
Otto Bretscher
Aug 31, 2015

Note that k = 1 150 ( 1 x k ) = f ( 1 ) = 151 \prod_{k=1}^{150}{(1-x_k)}=f(1)=151 , so that the sum we seek is 1 151 i < j k i , j ( 1 x k ) \frac{1}{151}\sum_{i<j}\prod_{k\neq{i,j}}(1-x_k) . If we consider the polynomial g ( x ) = x 151 1 g(x)=x^{151}-1 , with the additional root x 0 = 1 x_0=1 , then the sum we seek is 1 151 i < j < p k i , j , p ( 1 x k ) \frac{1}{151}\sum_{i<j<p}\prod_{k\neq{i,j,p}}(1-x_k) , a symmetric polynomial of degree 148 in the 151st roots of unity. The constant term of this polynomial is 1 151 ( 151 3 ) = 3725 \frac{1}{151}\dbinom{151}{3}=\boxed{3725} , and all the elementary symmetric polynomials of degree 1 through 150 vanish, by Viete.

Carlos Victor
Sep 5, 2015

the sum we want é S = ( 150 148 ) + ( 149 147 ) + + ( 2 0 ) 151 S= \dfrac{\binom{150}{148}+\binom{149}{147}+\cdots+\binom{2}{0}}{151}

or S = ( 151 148 ) 151 = 3725 S= \dfrac{ \binom{151}{148}}{151}= 3725 .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...