Summing a polynomial
If f ( n ) = n 4 − 1 0 n 3 + 3 5 n 2 − 5 0 n + 2 4 , calculate 1 9 1 ( n = 0 ∑ 9 9 f ( n ) − 5 ) .
Hint: f ( 1 0 0 ) = 9 0 3 4 5 0 2 4
The answer is 90345025.
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
f ( n ) = ( n − 1 ) ( n − 2 ) ( n − 3 ) ( n − 4 ) = 2 4 [ ( 4 n ) − ( 3 n ) + ( 2 n ) − ( 1 n ) + ( 0 n ) ]
OR
f ( n ) = n ( n 3 − 1 0 n 2 + 3 5 n − 5 0 ) + 2 4
= n [ ( n − 1 ) ( n 2 − 9 n + 2 6 ) − 2 4 ] + 2 4
= n [ ( n − 1 ) [ ( n − 2 ) ( n − 7 ) + 1 2 ] − 2 4 ] + 2 4
= n [ ( n − 1 ) [ ( n − 2 ) [ ( n − 3 ) − 4 ] + 1 2 ] − 2 4 ] + 2 4
= n ( n − 1 ) ( n − 2 ) ( n − 3 ) − 4 n ( n − 1 ) ( n − 2 ) + 1 2 n ( n − 1 ) − 2 4 n + 2 4
= 2 4 [ ( 4 n ) − ( 3 n ) + ( 2 n ) − ( 1 n ) + ( 0 n ) ] .
Hence,
∑ n = 0 m f ( n ) = 2 4 [ ( 5 m + 1 ) − ( 4 m + 1 ) + ( 3 m + 1 ) − ( 2 m + 1 ) + ( 1 m + 1 ) ]
= 2 4 ( 5 m + 1 ) − f ( m + 1 ) + 2 4 .
Therefore,
∑ n = 0 9 9 f ( n ) = 2 4 1 2 0 1 0 0 ∗ 9 9 ∗ 9 8 ∗ 9 7 ∗ 9 6 − f ( 1 0 0 ) + 2 4
= 2 0 ∗ ( 9 9 ∗ 9 8 ∗ 9 7 ∗ 9 6 ) − f ( 1 0 0 ) + 2 4 = 1 9 ∗ f ( 1 0 0 ) + 2 4 .
Finally,
1 9 ( ∑ n = 0 9 9 f ( n ) ) − 5 = 9 0 3 4 5 0 2 4 + 1 = 9 0 3 4 5 0 2 5 .
1 9 1 ( ∑ n = 0 9 9 ( f ( n ) ) − 5 ) ⇒ 9 0 3 4 5 0 2 5
( 0 + 0 + 0 + 0 + 2 4 ) + ( 1 + − 1 0 + 3 5 + − 5 0 + 2 4 ) + ( 1 6 + − 8 0 + 1 4 0 + − 1 0 0 + 2 4 ) + ( 8 1 + − 2 7 0 + 3 1 5 + − 1 5 0 + 2 4 ) + ( 2 5 6 + − 6 4 0 + 5 6 0 + − 2 0 0 + 2 4 ) + ( 6 2 5 + − 1 2 5 0 + 8 7 5 + − 2 5 0 + 2 4 ) + ( 1 2 9 6 + − 2 1 6 0 + 1 2 6 0 + − 3 0 0 + 2 4 ) + ( 2 4 0 1 + − 3 4 3 0 + 1 7 1 5 + − 3 5 0 + 2 4 ) + ( 4 0 9 6 + − 5 1 2 0 + 2 2 4 0 + − 4 0 0 + 2 4 ) + ( 6 5 6 1 + − 7 2 9 0 + 2 8 3 5 + − 4 5 0 + 2 4 ) + ( 1 0 0 0 0 + − 1 0 0 0 0 + 3 5 0 0 + − 5 0 0 + 2 4 ) + ( 1 4 6 4 1 + − 1 3 3 1 0 + 4 2 3 5 + − 5 5 0 + 2 4 ) + ( 2 0 7 3 6 + − 1 7 2 8 0 + 5 0 4 0 + − 6 0 0 + 2 4 ) + ( 2 8 5 6 1 + − 2 1 9 7 0 + 5 9 1 5 + − 6 5 0 + 2 4 ) + ( 3 8 4 1 6 + − 2 7 4 4 0 + 6 8 6 0 + − 7 0 0 + 2 4 ) + ( 5 0 6 2 5 + − 3 3 7 5 0 + 7 8 7 5 + − 7 5 0 + 2 4 ) + ( 6 5 5 3 6 + − 4 0 9 6 0 + 8 9 6 0 + − 8 0 0 + 2 4 ) + ( 8 3 5 2 1 + − 4 9 1 3 0 + 1 0 1 1 5 + − 8 5 0 + 2 4 ) + ( 1 0 4 9 7 6 + − 5 8 3 2 0 + 1 1 3 4 0 + − 9 0 0 + 2 4 ) + ( 1 3 0 3 2 1 + − 6 8 5 9 0 + 1 2 6 3 5 + − 9 5 0 + 2 4 ) + ( 1 6 0 0 0 0 + − 8 0 0 0 0 + 1 4 0 0 0 + − 1 0 0 0 + 2 4 ) + ( 1 9 4 4 8 1 + − 9 2 6 1 0 + 1 5 4 3 5 + − 1 0 5 0 + 2 4 ) + ( 2 3 4 2 5 6 + − 1 0 6 4 8 0 + 1 6 9 4 0 + − 1 1 0 0 + 2 4 ) + ( 2 7 9 8 4 1 + − 1 2 1 6 7 0 + 1 8 5 1 5 + − 1 1 5 0 + 2 4 ) + ( 3 3 1 7 7 6 + − 1 3 8 2 4 0 + 2 0 1 6 0 + − 1 2 0 0 + 2 4 ) + ( 3 9 0 6 2 5 + − 1 5 6 2 5 0 + 2 1 8 7 5 + − 1 2 5 0 + 2 4 ) + ( 4 5 6 9 7 6 + − 1 7 5 7 6 0 + 2 3 6 6 0 + − 1 3 0 0 + 2 4 ) + ( 5 3 1 4 4 1 + − 1 9 6 8 3 0 + 2 5 5 1 5 + − 1 3 5 0 + 2 4 ) + ( 6 1 4 6 5 6 + − 2 1 9 5 2 0 + 2 7 4 4 0 + − 1 4 0 0 + 2 4 ) + ( 7 0 7 2 8 1 + − 2 4 3 8 9 0 + 2 9 4 3 5 + − 1 4 5 0 + 2 4 ) + ( 8 1 0 0 0 0 + − 2 7 0 0 0 0 + 3 1 5 0 0 + − 1 5 0 0 + 2 4 ) + ( 9 2 3 5 2 1 + − 2 9 7 9 1 0 + 3 3 6 3 5 + − 1 5 5 0 + 2 4 ) + ( 1 0 4 8 5 7 6 + − 3 2 7 6 8 0 + 3 5 8 4 0 + − 1 6 0 0 + 2 4 ) + ( 1 1 8 5 9 2 1 + − 3 5 9 3 7 0 + 3 8 1 1 5 + − 1 6 5 0 + 2 4 ) + ( 1 3 3 6 3 3 6 + − 3 9 3 0 4 0 + 4 0 4 6 0 + − 1 7 0 0 + 2 4 ) + ( 1 5 0 0 6 2 5 + − 4 2 8 7 5 0 + 4 2 8 7 5 + − 1 7 5 0 + 2 4 ) + ( 1 6 7 9 6 1 6 + − 4 6 6 5 6 0 + 4 5 3 6 0 + − 1 8 0 0 + 2 4 ) + ( 1 8 7 4 1 6 1 + − 5 0 6 5 3 0 + 4 7 9 1 5 + − 1 8 5 0 + 2 4 ) + ( 2 0 8 5 1 3 6 + − 5 4 8 7 2 0 + 5 0 5 4 0 + − 1 9 0 0 + 2 4 ) + ( 2 3 1 3 4 4 1 + − 5 9 3 1 9 0 + 5 3 2 3 5 + − 1 9 5 0 + 2 4 ) + ( 2 5 6 0 0 0 0 + − 6 4 0 0 0 0 + 5 6 0 0 0 + − 2 0 0 0 + 2 4 ) + ( 2 8 2 5 7 6 1 + − 6 8 9 2 1 0 + 5 8 8 3 5 + − 2 0 5 0 + 2 4 ) + ( 3 1 1 1 6 9 6 + − 7 4 0 8 8 0 + 6 1 7 4 0 + − 2 1 0 0 + 2 4 ) + ( 3 4 1 8 8 0 1 + − 7 9 5 0 7 0 + 6 4 7 1 5 + − 2 1 5 0 + 2 4 ) + ( 3 7 4 8 0 9 6 + − 8 5 1 8 4 0 + 6 7 7 6 0 + − 2 2 0 0 + 2 4 ) + ( 4 1 0 0 6 2 5 + − 9 1 1 2 5 0 + 7 0 8 7 5 + − 2 2 5 0 + 2 4 ) + ( 4 4 7 7 4 5 6 + − 9 7 3 3 6 0 + 7 4 0 6 0 + − 2 3 0 0 + 2 4 ) + ( 4 8 7 9 6 8 1 + − 1 0 3 8 2 3 0 + 7 7 3 1 5 + − 2 3 5 0 + 2 4 ) + ( 5 3 0 8 4 1 6 + − 1 1 0 5 9 2 0 + 8 0 6 4 0 + − 2 4 0 0 + 2 4 ) + ( 5 7 6 4 8 0 1 + − 1 1 7 6 4 9 0 + 8 4 0 3 5 + − 2 4 5 0 + 2 4 ) + ( 6 2 5 0 0 0 0 + − 1 2 5 0 0 0 0 + 8 7 5 0 0 + − 2 5 0 0 + 2 4 ) + ( 6 7 6 5 2 0 1 + − 1 3 2 6 5 1 0 + 9 1 0 3 5 + − 2 5 5 0 + 2 4 ) + ( 7 3 1 1 6 1 6 + − 1 4 0 6 0 8 0 + 9 4 6 4 0 + − 2 6 0 0 + 2 4 ) + ( 7 8 9 0 4 8 1 + − 1 4 8 8 7 7 0 + 9 8 3 1 5 + − 2 6 5 0 + 2 4 ) + ( 8 5 0 3 0 5 6 + − 1 5 7 4 6 4 0 + 1 0 2 0 6 0 + − 2 7 0 0 + 2 4 ) + ( 9 1 5 0 6 2 5 + − 1 6 6 3 7 5 0 + 1 0 5 8 7 5 + − 2 7 5 0 + 2 4 ) + ( 9 8 3 4 4 9 6 + − 1 7 5 6 1 6 0 + 1 0 9 7 6 0 + − 2 8 0 0 + 2 4 ) + ( 1 0 5 5 6 0 0 1 + − 1 8 5 1 9 3 0 + 1 1 3 7 1 5 + − 2 8 5 0 + 2 4 ) + ( 1 1 3 1 6 4 9 6 + − 1 9 5 1 1 2 0 + 1 1 7 7 4 0 + − 2 9 0 0 + 2 4 ) + ( 1 2 1 1 7 3 6 1 + − 2 0 5 3 7 9 0 + 1 2 1 8 3 5 + − 2 9 5 0 + 2 4 ) + ( 1 2 9 6 0 0 0 0 + − 2 1 6 0 0 0 0 + 1 2 6 0 0 0 + − 3 0 0 0 + 2 4 ) + ( 1 3 8 4 5 8 4 1 + − 2 2 6 9 8 1 0 + 1 3 0 2 3 5 + − 3 0 5 0 + 2 4 ) + ( 1 4 7 7 6 3 3 6 + − 2 3 8 3 2 8 0 + 1 3 4 5 4 0 + − 3 1 0 0 + 2 4 ) + ( 1 5 7 5 2 9 6 1 + − 2 5 0 0 4 7 0 + 1 3 8 9 1 5 + − 3 1 5 0 + 2 4 ) + ( 1 6 7 7 7 2 1 6 + − 2 6 2 1 4 4 0 + 1 4 3 3 6 0 + − 3 2 0 0 + 2 4 ) + ( 1 7 8 5 0 6 2 5 + − 2 7 4 6 2 5 0 + 1 4 7 8 7 5 + − 3 2 5 0 + 2 4 ) + ( 1 8 9 7 4 7 3 6 + − 2 8 7 4 9 6 0 + 1 5 2 4 6 0 + − 3 3 0 0 + 2 4 ) + ( 2 0 1 5 1 1 2 1 + − 3 0 0 7 6 3 0 + 1 5 7 1 1 5 + − 3 3 5 0 + 2 4 ) + ( 2 1 3 8 1 3 7 6 + − 3 1 4 4 3 2 0 + 1 6 1 8 4 0 + − 3 4 0 0 + 2 4 ) + ( 2 2 6 6 7 1 2 1 + − 3 2 8 5 0 9 0 + 1 6 6 6 3 5 + − 3 4 5 0 + 2 4 ) + ( 2 4 0 1 0 0 0 0 + − 3 4 3 0 0 0 0 + 1 7 1 5 0 0 + − 3 5 0 0 + 2 4 ) + ( 2 5 4 1 1 6 8 1 + − 3 5 7 9 1 1 0 + 1 7 6 4 3 5 + − 3 5 5 0 + 2 4 ) + ( 2 6 8 7 3 8 5 6 + − 3 7 3 2 4 8 0 + 1 8 1 4 4 0 + − 3 6 0 0 + 2 4 ) + ( 2 8 3 9 8 2 4 1 + − 3 8 9 0 1 7 0 + 1 8 6 5 1 5 + − 3 6 5 0 + 2 4 ) + ( 2 9 9 8 6 5 7 6 + − 4 0 5 2 2 4 0 + 1 9 1 6 6 0 + − 3 7 0 0 + 2 4 ) + ( 3 1 6 4 0 6 2 5 + − 4 2 1 8 7 5 0 + 1 9 6 8 7 5 + − 3 7 5 0 + 2 4 ) + ( 3 3 3 6 2 1 7 6 + − 4 3 8 9 7 6 0 + 2 0 2 1 6 0 + − 3 8 0 0 + 2 4 ) + ( 3 5 1 5 3 0 4 1 + − 4 5 6 5 3 3 0 + 2 0 7 5 1 5 + − 3 8 5 0 + 2 4 ) + ( 3 7 0 1 5 0 5 6 + − 4 7 4 5 5 2 0 + 2 1 2 9 4 0 + − 3 9 0 0 + 2 4 ) + ( 3 8 9 5 0 0 8 1 + − 4 9 3 0 3 9 0 + 2 1 8 4 3 5 + − 3 9 5 0 + 2 4 ) + ( 4 0 9 6 0 0 0 0 + − 5 1 2 0 0 0 0 + 2 2 4 0 0 0 + − 4 0 0 0 + 2 4 ) + ( 4 3 0 4 6 7 2 1 + − 5 3 1 4 4 1 0 + 2 2 9 6 3 5 + − 4 0 5 0 + 2 4 ) + ( 4 5 2 1 2 1 7 6 + − 5 5 1 3 6 8 0 + 2 3 5 3 4 0 + − 4 1 0 0 + 2 4 ) + ( 4 7 4 5 8 3 2 1 + − 5 7 1 7 8 7 0 + 2 4 1 1 1 5 + − 4 1 5 0 + 2 4 ) + ( 4 9 7 8 7 1 3 6 + − 5 9 2 7 0 4 0 + 2 4 6 9 6 0 + − 4 2 0 0 + 2 4 ) + ( 5 2 2 0 0 6 2 5 + − 6 1 4 1 2 5 0 + 2 5 2 8 7 5 + − 4 2 5 0 + 2 4 ) + ( 5 4 7 0 0 8 1 6 + − 6 3 6 0 5 6 0 + 2 5 8 8 6 0 + − 4 3 0 0 + 2 4 ) + ( 5 7 2 8 9 7 6 1 + − 6 5 8 5 0 3 0 + 2 6 4 9 1 5 + − 4 3 5 0 + 2 4 ) + ( 5 9 9 6 9 5 3 6 + − 6 8 1 4 7 2 0 + 2 7 1 0 4 0 + − 4 4 0 0 + 2 4 ) + ( 6 2 7 4 2 2 4 1 + − 7 0 4 9 6 9 0 + 2 7 7 2 3 5 + − 4 4 5 0 + 2 4 ) + ( 6 5 6 1 0 0 0 0 + − 7 2 9 0 0 0 0 + 2 8 3 5 0 0 + − 4 5 0 0 + 2 4 ) + ( 6 8 5 7 4 9 6 1 + − 7 5 3 5 7 1 0 + 2 8 9 8 3 5 + − 4 5 5 0 + 2 4 ) + ( 7 1 6 3 9 2 9 6 + − 7 7 8 6 8 8 0 + 2 9 6 2 4 0 + − 4 6 0 0 + 2 4 ) + ( 7 4 8 0 5 2 0 1 + − 8 0 4 3 5 7 0 + 3 0 2 7 1 5 + − 4 6 5 0 + 2 4 ) + ( 7 8 0 7 4 8 9 6 + − 8 3 0 5 8 4 0 + 3 0 9 2 6 0 + − 4 7 0 0 + 2 4 ) + ( 8 1 4 5 0 6 2 5 + − 8 5 7 3 7 5 0 + 3 1 5 8 7 5 + − 4 7 5 0 + 2 4 ) + ( 8 4 9 3 4 6 5 6 + − 8 8 4 7 3 6 0 + 3 2 2 5 6 0 + − 4 8 0 0 + 2 4 ) + ( 8 8 5 2 9 2 8 1 + − 9 1 2 6 7 3 0 + 3 2 9 3 1 5 + − 4 8 5 0 + 2 4 ) + ( 9 2 2 3 6 8 1 6 + − 9 4 1 1 9 2 0 + 3 3 6 1 4 0 + − 4 9 0 0 + 2 4 ) + ( 9 6 0 5 9 6 0 1 + − 9 7 0 2 9 9 0 + 3 4 3 0 3 5 + − 4 9 5 0 + 2 4 ) ⇒ 1 7 1 6 5 5 5 4 8 0
1 9 1 7 1 6 5 5 5 4 8 0 − 5 ⇒ 9 0 3 4 5 0 2 5
Care to elaborate?
It really is as simple as add the one hundred function values for n from 0 to 99 ( N. B., the author corrected the summation range from 1 → 1 0 0 to 0 → 9 9 after a report against the problem), subtract 5 and divide the result by 19 to give the final result.
Log in to reply
So basically you just ask the computer to do the work, alright.
Log in to reply
After a half century of computer programming, starting with a mathematics problem no less, having an adequate home computer, they come naturally to me. Furthermore, I had to know what to tell the computer to do.
Some summation formulas: ∑ i = 0 n i j ⇒
0 1 2 3 4 5 6 7 8 9 n + 1 2 1 n ( n + 1 ) 6 1 n ( n + 1 ) ( 2 n + 1 ) 4 1 n 2 ( n + 1 ) 2 3 0 1 n ( n + 1 ) ( 2 n + 1 ) ( 3 n 2 + 3 n − 1 ) 1 2 1 n 2 ( n + 1 ) 2 ( 2 n 2 + 2 n − 1 ) 4 2 1 n ( n + 1 ) ( 2 n + 1 ) ( 3 n 4 + 6 n 3 − 3 n + 1 ) 2 4 1 n 2 ( n + 1 ) 2 ( 3 n 4 + 6 n 3 − n 2 − 4 n + 2 ) 9 0 1 n ( n + 1 ) ( 2 n + 1 ) ( 5 n 6 + 1 5 n 5 + 5 n 4 − 1 5 n 3 − n 2 + 9 n − 3 ) 2 0 1 n 2 ( n + 1 ) 2 ( n 2 + n − 1 ) ( 2 n 4 + 4 n 3 − n 2 − 3 n + 3 )
I put these summation formulas and more at Summation formulas for powers 0 to 20 of integers
Evaluated for the specific value of 99:
0 1 2 3 4 5 6 7 8 9 1 0 0 4 9 5 0 3 2 8 3 5 0 2 4 5 0 2 5 0 0 1 9 5 0 3 3 3 3 3 0 1 6 1 7 0 8 3 3 2 5 0 0 1 3 7 9 0 7 1 4 1 1 9 0 5 0 1 2 0 0 5 8 3 3 0 4 1 6 7 5 0 0 1 0 6 1 7 7 7 7 3 1 1 1 3 3 3 3 3 0 9 5 0 7 4 9 9 3 0 0 0 4 9 9 9 8 5 0 0
1 1 9 5 0 3 3 3 3 3 0 − 1 0 2 4 5 0 2 5 0 0 + 3 5 3 2 8 3 5 0 − 5 0 4 9 5 0 + 2 4 1 0 0 = 1 7 1 6 5 5 5 4 8 0
1 9 1 7 1 6 5 5 5 4 7 5 = 9 0 3 4 5 0 2 5
Log in to reply
@A Former Brilliant Member – Well, if a question posed in Brilliant is not tagged under the Computer Science category, I'd opt to use a minimal amount of computer work to solve this question.
Log in to reply
@Pi Han Goh – I understand that you are offended. I will continue to use available tools whether they be learned, researched or computed.
Log in to reply
@A Former Brilliant Member – No, I'm not offended at all. I just thought that you got some ingenious tricks up your sleeves when solving this question.
I actually quite enjoy most of the solutions that you've posted.
Cheers mate ;)
Log in to reply
@Pi Han Goh – Thank you. I usually label solutions when I have done an exhaustive computer solution. The label usually is "brute force solution." Sometimes, the brute force solution leads me to a clever solution. My math library here at home is several hundred books. I often go there for inspiration.
Since f ( n ) = ( n − 1 ) ( n − 2 ) ( n − 3 ) ( n − 4 ) , we have n = 0 ∑ 9 9 f ( n ) = 2 4 + n = 5 ∑ 9 9 f ( n ) = 2 4 + 2 4 n = 5 ∑ 9 9 f ( n ) / 2 4 = 2 4 + 2 4 n = 5 ∑ 9 9 ( 4 n − 1 ) . It is easy to show by induction (the "diagonal Pascal triangle" identity) that n = k + 1 ∑ ℓ ( k n − 1 ) = ( k + 1 ℓ ) . So we get n = 0 ∑ 9 9 f ( n ) = 2 4 + 2 4 ( 5 9 9 ) , so 1 9 1 ( n = 0 ∑ 9 9 f ( n ) − 5 ) = 1 9 1 ( 1 9 + 2 4 ( 5 9 9 ) ) = 1 + 1 9 2 4 5 ⋅ 2 4 9 9 ⋅ 9 8 ⋅ 9 7 ⋅ 9 6 ⋅ 9 5 = 1 + ( 9 9 ⋅ 9 8 ⋅ 9 7 ⋅ 9 6 ) = 1 + f ( 1 0 0 ) = 9 0 3 4 5 0 2 5 .