Inspired by Jake Lai

Algebra Level 4

Let r 1 , r 2 , r 3 , . . . , r 100 { r }_{ 1 },\quad { r }_{ 2 },\quad { r }_{ 3 },...,\quad { r }_{ 100 } be the roots of the polynomial

k = 0 100 ( 1 ) k F k + 1 x 100 k = x 100 x 99 + 2 x 98 . . . + F 101 \sum _{ k=0 }^{ 100 }{ { { \left( -1 \right) }^{ k }F }_{ k+1 }{ x }^{ 100-k } } ={ x }^{ 100 }-{ x }^{ 99 }+2{ x }^{ 98 }-...+{ F }_{ 101 }

Where F n { F }_{ n } is the n t h {n}^{th} number of the Fibonacci sequence.

Find the value of 1 i j 100 r i r j . \sum _{ 1\le i\le j\le 100 }^{ }{ { r }_{ i } } { r }_{ j }.


The answer is -1.

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

Jake Lai
Jan 13, 2015

First, observe the sum 1 i j 100 r i r j \displaystyle \sum _{1 \leq i \leq j \leq 100 } r_{i}r_{j} has the condition i j i \leq j . Thus, we can split it into

1 i < j 100 r i r j + k = 1 100 r k 2 \sum _{1 \leq i < j \leq 100 } r_{i}r_{j} + \sum _{k=1}^{100} r_{k}^{2}

Let the coefficients be a k = ( 1 ) k F k + 1 a_{k} = (-1)^{k}F_{k+1} . We deal with the first sum using Vieta's formulas:

1 i < j 100 r i r j = a 2 a 0 = 2 \sum _{1 \leq i < j \leq 100 } r_{i}r_{j} = \frac{a_{2}}{a_{0}} = 2

The second sum we resolve using Newton's identities:

k = 1 100 r k 2 = a 1 ( k = 1 100 r i ) 2 a 2 \sum _{k=1}^{100} r_{k}^{2} = a_{1} \left(\sum_{k=1}^{100} r_{i}\right)-2a_{2}

= 1 ( 1 ) 2 ( 2 ) = 3 = 1(1)-2(2) = -3

Summing the two, we get that

1 i j 100 r i r j = 1 i < j 100 r i r j + k = 1 100 r k 2 = 2 3 = 1 \sum _{1 \leq i \leq j \leq 100 } r_{i}r_{j} = \sum _{1 \leq i < j \leq 100 } r_{i}r_{j} + \sum _{k=1}^{100} r_{k}^{2} = 2-3 = \boxed{-1}

My gosh I didn't notice the \leq signs as opposed to the simple < < signs. This problem is very nice.

Milly Choochoo - 6 years, 4 months ago

What an overrated problem !

Rohit Shah - 6 years, 4 months ago

Log in to reply

Agreed! I initially rated it level 4, and then thought it was too high. Then it became level 5...

Julian Poon - 6 years, 4 months ago

Log in to reply

literally, that's not more than level 4! btw nyc format.

Akul Agrawal - 5 years, 5 months ago

1 i j 100 r i r j = k = 1 100 r k 2 + 1 i < j 100 r i r j = ( k = 1 100 r k ) 2 1 i < j 100 r i r j \displaystyle \sum_{1\leq i \leq j \leq 100} r_{i}r_{j} = \sum_{k=1}^{100} r_{k}^{2} +\sum_{1\leq i < j \leq 100} r_{i}r_{j} = \left ( \sum_{k=1}^{100} r_{k} \right )^{2} - \sum_{1\leq i < j \leq 100} r_{i}r_{j}

from vieta formula we know the answer is ( ( 1 ) ) 2 2 = 1 (-(-1))^{2}-2 = \boxed{-1}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...