Finite differences
MOPSS
28 April 2025
Mathematics Olympiad
Problem Solving Sessions
MOPSS
Department of Mathematics
IISER Bhopal
[Link]
Suggested readings
• Evan Chen’s advice On reading solutions, available at [Link]
[Link]/2017/03/06/on-reading-solutions/.
• Evan Chen’s Advice for writing proofs/Remarks on English, available at
[Link]
• Notes on proofs by Evan Chen from OTIS Excerpts [Che25, Chapter 1].
• Tips for writing up solutions by Edward Barbeau, available at https:
//[Link]/barbeau/[Link].
• Evan Chen discusses why math olympiads are a valuable experience for
high schoolers in the post on Lessons from math olympiads, available at
[Link]
List of problems and examples
1.1 Example (India RMO 2013b P3) . . . . . . . . . . . . . . . . 3
1.2 Example (Bay Area MO 12 2016 P4) . . . . . . . . . . . . . 4
§1 Finite differences
Note that
k 2 − (k − 1)2 = 2k − 1
holds for any integer k. In particular, given a positive integer n, we have
22 − 12 = 2 · 2 − 1,
32 − 22 = 2 · 3 − 1,
42 − 32 = 2 · 4 − 1,
··· = ··· ,
n − (n − 1)2 = 2 · n − 1.
2
Adding them, it follows that
n2 − 1 = 2(2 + 3 + · · · + n) − (n − 1),
which yields
n(n + 1)
1 + 2 + 3 + ··· + n = .
2
Consider the polynomial P (x) = x3 . Note that
P (k) − P (k − 1) = 3k 2 − 3k + 1.
Using a similar argument as above, it follows that given a positive integer n,
we have
13 − 03 = 3 · 12 − 3 · 1 + 1,
23 − 13 = 3 · 22 − 3 · 2 + 1,
33 − 23 = 3 · 32 − 3 · 3 + 1,
43 − 33 = 3 · 42 − 3 · 4 + 1,
··· = ··· ,
n − (n − 1)3 = 3 · n2 − 3 · n + 1.
3
Adding them, it follows that
n3 = 3(1 + 22 + 32 + · · · + n2 ) − 3(1 + 2 + 3 + · · · + n) + n,
2
1 Finite differences Typos may be reported to jpsaha@[Link].
which yields
n3 − n
1 + 2 2 + 3 2 + · · · + n2 = + (1 + 2 + 3 + · · · + n)
3
n3 − n n(n + 1)
= +
3 2
1
= n(n + 1)(2n + 1).
6
Example 1.1 (India RMO 2013b P3). Consider the expression
20132 + 20142 + 20152 + · · · + n2 .
Prove that there exists a natural number n > 2013 for which one can change a
suitable number of plus signs to minus signs in the above expression to make
the resulting expression equal 9999.
Summary — “Differentiating” a polynomial enough times makes it linear.
Walkthrough —
(a) Consider the polynomial P (k) = k2 , and the polynomial Q(k) := P (k) −
(k − 1).
(b) Since Q(k) is a linear polynomial in k, the difference R(k) := Q(k) −
Q(k − 2) is a constant, that is, it does not depend on k.
(c) Note that R(k) is a ±1-linear combinationa of four consecutive squares.
(d) Does this help?
aWhat does it mean?
Solution 1. Consider the polynomial P (k) = k 2 , and the polynomial Q(k) :=
P (k) − (k − 1). Since Q(k) is a linear polynomial in k, the difference R(k) :=
Q(k) − Q(k − 2) is a constant, that is, it does not depend on k. Indeed,
Q(k) = 2k−1, and R(k) = 4. Note that R(k) = k 2 −(k−1)2 −(k−2)2 +(k−3)2 .
Note that
20132 + 20142 + 20152 + 20162 + 20172 > 9999
holds, and the integers 20132 +20142 +20152 +20162 +20172 , 9999 are congruent
modulo 4, that is, they differ by a multiple of 4. Let m ≥ 1 be an integer such
that
9999 = 20132 + 20142 + 20152 + 20162 + 20172 − 4m
holds. Since
−k 2 + (k + 1)2 + (k + 2)2 − (k + 3)2 = −4,
Some style files, prepared by Evan Chen, have been adapted here. 3
28 April 2025 [Link]
it follows that
9999
= 20132 + 20142 + 20152 + 20162 + 20172
− 20182 + 20192 + 20202 − 20212
− ...
− (2018 + 4(m − 1))2 + (2019 + 4(m − 1))2
+ (2020 + 4(m − 1))2 − (2021 + 4(m − 1))2 .
It follows that there exists a natural number n = 2021 + 4(m − 1) > 2013, for
which one can change a suitable number of plus signs to minus signs in the
expression
20132 + 20142 + 20152 + · · · + n2
to make the resulting expression equal to 9999. ■
Example 1.2 (Bay Area MO 12 2016 P4). Find a positive integer N and
a1 , a2 , . . . , aN , where ak = 1 or ak = −1 for each k = 1, 2, . . . , N , such that
a1 · 13 + a2 · 23 + a3 · 33 + · · · + aN · N 3 = 20162016,
or show that this is impossible.
Summary — “Differentiating” a polynomial enough times makes it linear.
Walkthrough —
(a) Consider the polynomial P (k) := k3 . Note that R(k) := P (k) − P (k − 1)
is a quadratic polynomial in k.
(b) Also note that S(k) := R(k) − R(k − 2) is a linear polynomial in k.
Solution 2. Consider the polynomial P (k) := k 3 . Note that R(k) := P (k) −
P (k − 1) is equal to 3k 2 − 3k + 1. Also note that S(k) := R(k) − R(k − 2)
is equal to 6(2k − 2) − 6. This gives S(k) − S(k − 4) = 48. It follows that
some ±1-linear combination of any given eight consecutive cubes is equal to
48. More specifically,
k 3 − (k − 1)3 − (k − 2)3 + (k − 3)3 − (k − 4)3 + (k − 5)5 + (k − 6)3 − (k − 7)3 = 48,
or equivalently,
−k 3 +(k +1)3 +(k +2)3 −(k +3)3 −(k +4)3 +(k +5)3 +(k +6)3 −(k +7)3 = 48.
4 The content posted here and at this blog by Evan Chen are quite useful.
References Typos may be reported to jpsaha@[Link].
Note that 20162016 is divisible by 3 and 16. Since 3, 16 do not have any
common prime factor, it follows that 20162016 is a multiple of 48. Write
f (k) = −k 3 +(k+1)3 +(k+2)3 −(k+3)3 −(k+4)3 +(k+5)3 +(k+6)3 −(k+7)3 .
Note that
f (1) + f (9) + f (17) + · · · + f (8m − 7) = 20162016,
where m denotes the integer 20162016/48. We conclude that one may take
N = 8m = 20162016/6 = 3360336 so that the given condition holds. ■
References
[Che25] Evan Chen. The OTIS Excerpts. Available at https : / / web .
[Link]/[Link]. 2025, pp. vi+289
Some style files, prepared by Evan Chen, have been adapted here. 5
