. . . . . . . . . . . . . . . . . . . . . . . . . .
Olympiad Training for Individual Study
Write Down Formulas!
Based on a MOP class of the same name by Yang P. Liu
Evan Chen《陳誼廷》
14 March 2025
》
ZAW-FORMULAS
廷
誼 se
陳 U
n《 al
h e rn
C nt e
n
a , I
Ev I S
y
B O T
OTIS, © Evan Chen, internal use only. Artwork contributed by Alex Zhao.
1
Evan Chen《陳誼廷》 (OTIS, updated 2025-03-14) Write Down Formulas!
§1 Lecture notes
Sometimes, you should just write things out.
This unit isn’t quite like the Grinding unit. In Grinding, there is a lot more set-up:
you often have to figure out how you want to set up cases to minimize the amount of
calculation you want to do. In this Formulas unit, you will often not really have cases at
all. You still have to be careful, but often not because of casework, but because you’re
manipulating a double or triple sum that’s not that intuitive. Often the computation
feels linear.
Here’s a picture in my head to describe the difference. The casework from Grinding
is wide but shallow: each individual case is easy and self-contained, but there’s a lot of
them. But here the computations from Formulas is narrow but deep: you write down one
big formula and then go after it for a page or two. Complex numbers in geometry feels
》
more like the latter,Pif you are used to it.
Expect plenty of signs to join the party. A lot of these problems would also fit in
廷
Sums unit, but often here the sums aren’t set up for you.
誼 se
§1.1 Walkthroughs — Cayley’s Theorem
陳 U
There isn’t any particular theory I need to cover, so rather I want to use these walkthroughs
to make a rather political statement: Cayley’s formula is best proved by formulas.
《 al
The theorem statement is:
n
e rn
Theorem (Cayley’s formula)
h
The number of labeled trees on n vertices is nn−2 .
C t e
Most proofs of this theorem that you will see in the literature are bijective1 or quote
n
n I
some theorems from enumerative combinatorics (Kirchhoff’s matrix tree theorem for
va ,
example). For you, an olympiad high school student, I don’t think either of these are the
S
easiest to come up with.
E I
Instead, here are two problems which I definitely think you can solve yourself, and
y T
which imply the result.
B O
Example 1.1
Let G be a simple graph with k connected components, which have a1 , . . . , ak
vertices, respectively. Count the number of ways to add k − 1 edges to G to form a
connected graph.
Z6F1A1FD Walkthrough. We let g(a1 , . . . , ak ) denote the answer. (Cayley’s formula is then the
assertion that g(1, . . . , 1) = k k−2 .)
(a) Compute g(a, b).
(b) Show that g(a, b, c) = abc(a + b + c).
(c) Prove that
X 1 1 2 2
3
g(a, b, c, d) = a bcd + a b cd .
sym
6 2
Factor the resulting expression.
1
For example, https://blog.evanchen.cc/2017/09/04/joyals-proof-of-cayleys-tree-formula/ is
the cleanest proof I know.
2
Evan Chen《陳誼廷》 (OTIS, updated 2025-03-14) Write Down Formulas!
(d) Come up with a conjecture for g(a1 , . . . , ak ) (keeping in mind the desired answer
k k−2 for g(1, . . . , 1)).
For the induction, it’s actually easier to do the casework if you assume the edges have
some order (hence multiplying by a factor of (k − 1)!). So let f(a1 , . . . , ak ) be the number
of ways to add k − 1 edges, in order.
(e) Prove considering where to place the first edge gives you the recursion
X
f(a1 , . . . , ak ) = ai aj f(ai + aj , a1 , . . . , ak )
| {z }
1≤i<j≤k missing ai and aj
(f) Now just power through the calculation to complete the induction.
》
廷
Example 1.2
Let d1 , . . . , dn be positive integers with i di = 2n − 2. Find the number of labeled
P
誼 se
trees on n vertices such that the degree of the ith vertex is di .
陳 U
Z03DB838 Walkthrough. I’ll even tell you what the answer is this time:
《 al
(n − 2)! n−2
n
= .
(d1 − 1)! . . . (dn − 1)! d1 − 1, . . . , dn − 1
h e rn
Prove it by induction, in the same way as the previous example.
C t e
The latter result also implies Cayley’s formula by the multinomial theorem.
n
a , I n
§1.2 Commentary
v
So the reflexes I want you to pick up from this unit are when it’s possible to solve a
E I S
problem simply by doing enough calculations (somewhat different from casework). This
is more often possible than people suspect. The previous walkthroughs are thus good
y T
examples in the sense that you look at them, and once you have the conjectured answer
B O
(and maybe even before that), you feel like the natural recursion you have should be good
enough to just solve the problem.
The issue of course is that, well, you can’t tell by looking, because the calculation is
probably long enough that it won’t fit your memory. No worries, that’s what paper is for!
Some untested philosophy:
• I think roughly you can think of these as problems that would be easy if you had
infinite working memory (which is different from infinite computational power). I
don’t think these calculations are long in the same sense that a complex numbers
calculation is long. My opinion is that actually they are “short” in the number of
equals signs. They are just hard to think about because most people are not really
able to manipulate n-variable multi-sums in their head, which is why being able to
write is so helpful here.
• You will actually not swap the order of summation as often you as you might expect
from the Sums unit.
3
Evan Chen《陳誼廷》 (OTIS, updated 2025-03-14) Write Down Formulas!
• Recursion and strengthened induction go well with this unit. It’s almost like, you
can actually describe what you want completely, it just takes a lot of symbols? For
example in the previous problems, we had a real recursion that did what we wanted;
it just happens to take a fairly dense notation to write down, but the essence is
fairly routine.
From a linguistic point of view, this is why mathematical notation is so powerful,
because it lets you concisely express content that would not be possible in the
English language. It is less natural this way, but better than not expressible at all.
§1.3 Long walkthrough (due to Michael Ren)
Example 1.3 (USAMO 2017/2)
》
Let m1 , m2 , . . . , mn be a collection of n positive integers, not necessarily distinct.
For any sequence of integers A = (a1 , . . . , an ) and any permutation w = w1 , . . . , wn
廷
of m1 , . . . , mn , define an A-inversion of w to be a pair of entries wi , wj with i < j
for which one of the following conditions holds:
誼 se
• ai ≥ wi > wj ,
陳 U
• wj > ai ≥ wi , or
《 al
• wi > w j > a i .
n
e rn
Show that, for any two sequences of integers A = (a1 , . . . , an ) and B = (b1 , . . . , bn ),
h
and for any positive integer k, the number of permutations of m1 , . . . , mn having
C e
exactly k A-inversions is equal to the number of permutations of m1 , . . . , mn having
t
exactly k B-inversions.
17AMO2
n
a , I n
Walkthrough. It suffices to prove the result for B = (0, . . . , 0) by transitivity; such
v
pairs (i, j) (satisfying i < j and wi > wj ) are inversions; see https://en.wikipedia.
E I S
org/wiki/Inversion_(discrete_mathematics).
There isn’t a good closed form for the number of permutations on {1, . . . , n} with
y T
exactly k inversions, but there is a good generating function for it (which is even better
B O
for our purposes, since we only want to show equality!), and we’ll use that to do all our
computation:
(a) Let n be a positive integer. Prove that the coefficient of q s in the generating
function
n!q = 1 · (1 + q) · (1 + q + q 2 ) · · · · · (1 + q + q 2 + · · · + q n−1 )
is equal to the number of permutations on {1, . . . , n} with exactly s inversions.
(Most likely, you will use induction on n. This is called the q-factorial.)
Unfortunately, in the present problem the given numbers we are permuting need not be
distinct and this will be a significant headache. We take our given multiset M of n positive
integers, we suppose the distinct numbers are θ1 < θ2 < · · · < θm . (In what follows we
count permutations on M with multiplicity: so M = {1, 1, 2} still has 3! = 6 permutations
total.) We let ei be the number of times θi appears. Therefore the multiplicities ei should
have sums
e1 + · · · + em = n
and m denotes the number of distinct elements.
4
Evan Chen《陳誼廷》 (OTIS, updated 2025-03-14) Write Down Formulas!
Finally, we let
q number inversions of σ
X
F(e1 , . . . , em ) =
perms σ
be the associated generating function for the number of inversions. For example, the first
claim we proved says that F(1, . . . , 1) = n!q .
(b) Optional warm-up: compute F(2, 1, . . . , 1). Solving this will make the next part
| {z }
n−2
more natural.
(c) Compute F(e1 , . . . , em ). This is an overcounting argument: try to show you have
an overcount of eii !q for each i, by imagining what happens if you arbitrarily force
e!
some order on those ei equal elements (in one of ei ! ways).
》
(d) Verify that
廷
ei · F(e1 , . . . , ei − 1, . . . , em ) 1 − q ei
=
F(e1 , . . . , em ) 1 − qn
誼 se
to check your work; we’ll use this later in our calculation.
陳 U
So, we now have the generating function that counts the answer when B = (0, . . . , 0).
The problem tells us to prove the same generating function works for any random sequence
《 al
A. The proof is again an ugly induction on n.
n
For the inductive step, fix A, and assume the first element satisfies θk ≤ a1 < θk+1 (so
e rn
0 ≤ k ≤ m; we for convenience set θ0 = −∞ and θm = +∞). We count the permutations
h
based on what the first element θi of the permutation is.
C t e
(e) Show that if 1 ≤ i ≤ k we get a contribution of
n
n
a , I
q (e1 +···+ei−1 )+(ek+1 +···+em ) · ei · F(e1 , . . . , ei − 1, . . . , em )
Ev I S
(f) Show that if k + 1 ≤ i ≤ n we get a contribution of
y T
q ek+1 +···+ei−1 · ei · F(e1 , . . . , ei − 1, . . . , em ).
B O
So, we have two massive sums over i, and we want to show the sum equals F(e1 , . . . , em ).
(g) Divide out by F(e1 , . . . , em ) to get some identity, and verify it telescopes.
5
Evan Chen《陳誼廷》 (OTIS, updated 2025-03-14) Write Down Formulas!
§2 Practice problems
Instructions: Solve [42♣]. If you have time, solve [56♣]. Problems with red weights are mandatory.
I understand my tests are popular reading in the teachers’
lounge.
Calvin in Calvin and Hobbes
16CHNTST24
[2♣] Problem 1 (China TST 2016/2/4). For every positive integer m = 2k t, where
k ≥ 0 and t is odd, we let f(m) = t1−k . Prove that for any positive integers a ≤ m with
a odd, the number f(1)f(2) . . . f(m) is an integer divisible by a.
05SLN3
[3♣] Problem 2 (Shortlist 2005 N3). Let a, b, c, d, e, f be positive integers. Assume
》
that S = a + b + c + d + e + f divides both abc + def and ab + bc + ca − de − ef − f d.
Prove that S is composite.
廷
25OIMEI15
[5♣] Problem 3 (OTIS Mock AIME I 2025/15, by Abel George Mathew). Alice has a
誼 se
deck of 2000 cards, numbered 1 through 2000. Alice chooses an integer 1 ≤ n < 1000
and deals Cheshire a random subset of 2n − 1 of the cards without repetition. Cheshire
陳 U
wins if the cards dealt contain any n consecutively numbered cards. Compute the value
of n Alice should choose to minimize Cheshire’s chances of winning.
《 al
15PTNMA4
n
[3♣] Problem 4 (Putnam 2015 A4). For a real number x, let Sx denote the set of
e rn
positive integers n such that bnxc is even. Find the value of
C h e
!
X 1
inf
t
.
2n
n
x∈[0,1)
n
n∈Sx
a , I
18TSTST6
[3♣] Problem 5 (TSTST 2018/6). Let S = {1, . . . , 100}, and for every positive integer
v
n define
E I S
Tn = {(a1 , . . . , an ) ∈ S n | a1 + · · · + an ≡ 0 (mod 100)} .
y T
Determine which n have the following property: if we color any 75 elements of S red,
then at least half of the n-tuples in Tn have an even number of coordinates with red
B O
elements.
21TSTST4
[3♣] Problem 6 (TSTST 2021/4). Let a and b be positive integers. Suppose that there
are infinitely many pairs of positive integers (m, n) for which m2 + an + b and n2 + am + b
are both perfect squares. Prove that a divides 2b.
07SLN4
[5♣] Problem 7 (Shortlist 2007 N4). Let n ≥ 2 be an integer and let
n+1 n
2 2
N= n
− n−1 .
2 2
Compute ν2 (N) in terms of n.
19USATST2
[5♣] Problem 8 (USA TST 2019/2). Let Z/nZ denote the set of integers considered
modulo n (hence Z/nZ has n elements). Find all positive integers n for which there
exists a bijective function g : Z/nZ → Z/nZ, such that the 101 functions
g(x), g(x) + x, g(x) + 2x, ..., g(x) + 100x
are all bijections on Z/nZ.
6
Evan Chen《陳誼廷》 (OTIS, updated 2025-03-14) Write Down Formulas!
18AMO3
[9♣] Problem 9 (USAMO 2018/3). Let n ≥ 2 be an integer, and let {a1 , . . . , am } denote
the m = ϕ(n) integers less than n and relatively prime to n. Assume that every prime
divisor of m also divides n. Prove that m divides ak1 + · · · + akm for every positive integer
k.
17HMMTT9
[5♣] Problem 10 (HMMT 2017 T9). Let n > 2 be an odd positive integer, and consider
a regular n-gon G in the plane centered at the origin. Let a subpolygon P be a polygon
with at least 3 vertices whose vertex set is a subset of that of G. Say P is well-centered if
its centroid is the origin. Also, say P is decomposable if its vertex set can be written as
the disjoint union of regular polygons with at least 3 vertices.
Show that all well-centered subpolygons are decomposable if and only if n has at most
two distinct prime divisors.
》
21TSTST3
[5♣] Problem 11 (TSTST 2021/3). Find all positive integers k > 1 for which there
exists a positive integer n such that k is divisible by n, and m is not divisible by n
廷
n n
for 2 ≤ m < k.
誼 se
14SLN6
[5♣] Problem 12 (Shortlist 2014 N6). Let a1 < a2 < · · · < an be pairwise coprime
positive integers with a1 being prime and a1 ≥ n + 2. On the segment I = [0, a1 a2 · · · an ]
陳 U
of the real line, mark all integers that are divisible by at least one of the numbers a1 , . . . ,
an . These points split I into a number of smaller segments. Prove that the sum of the
《 al
squares of the lengths of these segments is divisible by a1 .
n
e rn
15PTNMA5
[5♣] Problem 13 (Putnam 2015 A5). Let q ≥ 1 be an odd integer and define
C h e
Nq = # {0 < a < q/4 | gcd(a, q) = 1} .
n nt
Prove Nq is odd if and only if q = pk for some prime p ≡ 5, 7 (mod 8) and k > 0.
I
a ,
17PTNMB6
v
[9♣] Required Problem 14 (Putnam 2017 B6). Find the number of ordered 64-tuples
S
(x0 , . . . , x63 ) of distinct elements of {1, . . . , 2017} which satisfy
13JANTST3
y E T I
x0 + x1 + 2x2 + 3x3 + · · · + 63x63 ≡ 0 (mod 2017).
B O
[5♣] Problem 15 (January TST 2013/3). In a table with n rows and 2n columns
where n is a fixed positive integer, we write either zero or one into each cell so that
each row has n zeros and n ones. For 1 ≤ k ≤ n and 1 ≤ i ≤ n, we define ak,i so that
the ith zero in the kth row is the ak,i th column. Let F be the set of such tables with
a1,i ≥ a2,i ≥ · · · ≥ an,i for every i with 1 ≤ i ≤ n. We associate another n × 2n table
f(C) for each C ∈ F as follows: for the kth row of f(C), we write n ones in the columns
an,k − k + 1, an−1,k − k + 2, . . . , a1,k − k + n (and we write zeros in the other cells in the
row).
(a) Show that f(C) ∈ F.
(b) Show that f(f(f(f(f(f(C)))))) = C for any C ∈ F.
17ELMO6
[5♣] Problem 16 (ELMO 2017/6). Find all functions f : R → R such that for all real
numbers a, b, and c:
(i) If a + b + c ≥ 0 then f(a3 ) + f(b3 ) + f(c3 ) ≥ 3f(abc).
(ii) If a + b + c ≤ 0 then f(a3 ) + f(b3 ) + f(c3 ) ≤ 3f(abc).
7
Evan Chen《陳誼廷》 (OTIS, updated 2025-03-14) Write Down Formulas!
03IMO5
[3♣] Problem 17 (IMO 2003/5). Let n be a positive integer and let x1 ≤ x2 ≤ · · · ≤ xn
be real numbers. Prove that
2
n X n n n
X 2(n2 − 1) X X
|xi − xj | ≤ (xi − xj )2
3
i=1 j=1 i=1 j=1
with equality if and only if x1 , x2 , . . . , xn form an arithmetic sequence.
18CHN3
[5♣] Required Problem 18 (China 2018/3). Let q be a positive integer which is not
a perfect cube. Prove that there exists a positive constant C such that for all natural
numbers n, one has
1 2 1
{nq 3 } + {nq 3 } ≥ Cn− 2
》
where {x} denotes the fractional part of x.
廷
[1♣] Mini Survey. Fill out feedback on the OTIS-WEB portal when submitting this
誼 se
problem set. Any thoughts on problems (e.g. especially nice, instructive, easy, etc.) or
overall comments on the unit are welcome.
陳 U
In addition, if you have any suggestions for problems to add, or want to write hints for
one problem you really liked, please do so in the ARCH system!
《 al
The maximum number of [♣] for this unit is [86♣], including the mini-survey.
n
e rn
C h e
n I nt
va ,
E I S
y
B O T
8
Evan Chen《陳誼廷》 (OTIS, updated 2025-03-14) Write Down Formulas!
§3 Solutions to the walkthroughs
§3.1 Solution 1.1
The answer is
a1 . . . ak (a1 + · · · + ak )k−2
which generalizes Cayley’s formula!
We will show that
f(a1 , . . . , ak ) = (k − 1)!(a1 . . . ak )(a1 + · · · + ak )k−2
counts the number of ways to pick k−1 edges, in order. The proof is by induction on k, with
k = 1 being clear. If we add an edge between the first and second connected components,
there are a1 a2 ways to do so, and the number of ways to finish is f(a1 + a2 , a3 . . . , ak ). So
》
廷
X
f(a1 , . . . , ak ) = ai aj f(ai + aj , a1 , . . . , ak )
| {z }
1≤i<j≤k missing ai and aj
誼 se
X
k−2
= (k − 2)! (ai + aj )(a1 . . . ak )(a1 + · · · + ak )
陳 U
1≤i<j≤k
X
= (k − 2)!(a1 . . . ak )(a1 + · · · + ak )k−2 (ai + aj )
《 al
1≤i<j≤k
n
k−1
= (k − 1)!(a1 . . . ak )(a1 + · · · + ak ) .
h e rn
§3.2 Solution 1.2
C t e
The answer is
n n
(n − 2)! n−2
I
= .
a ,
(d1 − 1)! . . . (dn − 1)! d1 − 1, . . . , dn − 1
v
This can be proven by induction, with the base case n = 2 being trivial.
E S
Now assume n ≥ 3. Since di are positive integers with average 2 − 2/n < 2, we may
I
WLOG assume dn = 1 (a leaf of the tree). So by deleting the leaf, the trees on {1, . . . , n}
y T
with a leaf at n are in bijection with trees on {1, . . . , n − 1} where one of the vertices k
B O
has its degree decreased by one.
Hence, by induction hypothesis, the number of trees is
n−1
X (n − 3)!
(d1 − 1)! . . . (dk−1 − 1)!(dk − 2)!(dk+1 − 1)! . . . (dn−1 − 1)!
k=1
n−1
X (n − 3)!
= · (dk − 1)
(d1 − 1)! . . . (dn−1 − 1)!
k=1
n−1
(n − 3)! X
= (dk − 1)
(d1 − 1)! . . . (dn−1 − 1)!
k=1
(n − 3)!
= [(2n − 2) − n]
(d1 − 1)! . . . (dn−1 − 1)!
(n − 2)! (n − 2)!
= = .
(d1 − 1)! . . . (dn−1 − 1)! (d1 − 1)! . . . (dn − 1)!
Here we adopt the convention that (−1)! = ∞, corresponding to the cases where dk = 1
above.
9
Evan Chen《陳誼廷》 (OTIS, updated 2025-03-14) Write Down Formulas!
Remark. By summing across all choices of di , we get n−2
P
d1 +···+dn =n+(n−2) d1 −1,...,dn −1 =
nn−2 via the multinomial theorem.
§3.3 Solution 1.3, USAMO 2017/2
The following solution was posted by Michael Ren, and I think it is the most natural one
(since it captures all the combinatorial ideas using a q-generating function that is easier
to think about, and thus makes the problem essentially a long computation).
Denote by M our multiset of n positive integers. Define an inversion of a permutation to
be pair i < j with wi < wj (which is a (0, . . . , 0)-inversion in the problem statement); this
is the usual definition (see https://en.wikipedia.org/wiki/Inversion_(discrete_
mathematics)). So we want to show the number of A-inversions is equal to the number
》
of usual inversions. In what follows we count permutations on M with multiplicity: so
M = {1, 1, 2} still has 3! = 6 permutations.
廷
We are going to do what is essentially recursion, but using generating functions in
a variable q to do our book-keeping. (Motivation: there’s no good closed form for the
誼 se
number of inversions, but there’s a great generating function known — which is even
陳 U
better for us, since we’re only trying to show two numbers are equal!) First, we prove
two claims.
《 al
Claim — For any positive integer n, the generating function for the number of
n
permutations of (1, 2, . . . , n) with exactly k inversions is
h e rn n!q := 1 · (1 + q) · (1 + q + q 2 ) · . . . (1 + q + · · · + q n−1 ).
C t e
Here we mean that the coefficient of q s above gives the number of permutations with
n n
exactly s inversions.
va , I
Proof. This is an induction on n, with n = 1 being trivial. Suppose we choose the first
S
element to be i, with 1 ≤ i ≤ n. Then there will always be exactly i − 1 inversions
E I
using the first element, so this contributes q i · (n − 1)!q . Summing 1 ≤ i ≤ n gives the
y T
result.
B O
Unfortunately, the main difficulty of the problem is that there are repeated elements,
which makes our notation much more horrific.
Let us define the following. We take our given multiset M of n positive integers, we
suppose the distinct numbers are θ1 < θ2 < · · · < θm . We let ei be the number of times
θi appears. Therefore the multiplicities ei should have sums
e1 + · · · + em = n
and m denotes the number of distinct elements. Finally, we let
q number inversions of σ
X
F(e1 , . . . , em ) =
permutations σ
be the associated generating function for the number of inversions. For example, the first
claim we proved says that F(1, . . . , 1) = n!q .
10
Evan Chen《陳誼廷》 (OTIS, updated 2025-03-14) Write Down Formulas!
Claim — We have the explicit formula
m
Y ei !
F(e1 , . . . , em ) = n!q · .
ei !q
i=1
Proof. First suppose we perturb all the elements slightly, so that they are no longer equal.
Then the generating function would just be n!q .
Then, we undo the perturbations for each group, one at a time, and claim that we get
the above ei !q factor each time. Indeed, put the permutations into classes of e1 ! each
where permutations in the same classes differ only in the order of the perturbed θ1 ’s
(with the other n − e1 elements being fixed). Then there is a factor of e1 !q from each class,
owing to the slightly perturbed inversions we added within each class. So we remove that
factor and add e1 ! · q 0 instead. This accounts for the first term of the product.
》
Repeating this now with each term of the product implies the claim.
廷
Thus we have the formula for the number of inversions in general. We wish to show
this also equals the generating function the number of A-inversions, for any fixed choice
誼 se
of A. This will be an induction by n, with the base case being immediate.
For the inductive step, fix A, and assume the first element satisfies θk ≤ a1 < θk+1 (so
陳 U
0 ≤ k ≤ m; we for convenience set θ0 = −∞ and θm = +∞). We count the permutations
based on what the first element θi of the permutation is. Then:
《 al
• Consider permutations starting with θi ∈ {θ1 , . . . , θk }. Then the number of inver-
n
e rn
sions which will use this first term is (e1 + · · · + ei−1 ) + (ek+1 + · · · + em ). Also, there
h
are ei ways to pick which θi gets used as the first term. So we get a contribution of
C e
q e1 +···+ei−1 +(ek+1 +···+em ) · ei · F(e1 , . . . , ei − 1, . . . , em )
n nt
in this case (with inductive hypothesis to get the last F-term).
a , I
• Now suppose θi ∈ {θk+1 , . . . , θm }. Then the number of inversions which will use
v
this first term is ek+1 + · · · + ei−1 . Thus by a similar argument the contribution is
E I S
q ek+1 +···+ei−1 · ei · F(e1 , . . . , ei − 1, . . . , em ).
y T
Therefore, to complete the problem it suffices to prove
B O
k
X
q (e1 +···+ei−1 )+(ek+1 +···+em ) · ei · F(e1 , . . . , ei − 1, . . . , em )
i=1
m
X
+ q ek+1 +···+ei−1 · ei · F(e1 , . . . , ei − 1, . . . , em )
i=k+1
= F(e1 , . . . , em ).
Now, we see that
ei · F(e1 , . . . , ei − 1, . . . , em ) 1 + · · · + q ei −1 1 − q ei
= =
F(e1 , . . . , em ) 1 + q + · · · + q n−1 1 − qn
so it’s equivalent to show
k
X m
X
n ek+1 +···+em e1 +···+ei−1 ei
1−q =q q (1 − q ) + q ek+1 +···+ei−1 (1 − q ei )
i=1 i=k+1
which is clear, since the left summand telescopes to q ek+1 +···+em − q n and the right
summand telescopes to 1 − q ek+1 +···+em .
11
Evan Chen《陳誼廷》 (OTIS, updated 2025-03-14) Write Down Formulas!
Remark. Technically, we could have skipped straight to the induction, without proving the
first two claims. However I think the solution reads more naturally this way.
》
廷
誼 se
陳 U
n《 al
h e rn
C nt e
n
a , I
Ev I S
y
B O T
12
