Exam (elaborations)
Summations By Evan Chen
- Course
- Institution
Summations By Evan Chen
[Show more]
Seller
Follow
modockochieng06
Content preview
SummationsEvan Chen
October 13, 2016
Mathematicians just love sigma notation for two reasons. First, it provides a convenient
way to express a long or even infinite series. But even more important, it looks really
cool and scary, which frightens nonmathematicians into revering mathematicians and
paying them more money.
— Calculus II for Dummies
Acknowledgments
Thanks to Zack Chroman, Michael Diao, Steven Hao, Ryan Kim, Kevin Qian, Colin
Tang, Michael Tang, Tyler Zhu, for helpful suggestions and comments.
Contents
1 Introduction 2
2 Algebraic manipulation 2
2.1 Telescoping and partial fractions . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Swapping the order of summation . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Finite Fourier analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Sums modulo a prime 8
3.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 Multiplicative number theory 10
4.1 Multiplicative functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2 Dirichlet convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3 Möbius inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5 Generating functions 13
5.1 Toy applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.2 Linear recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.3 Common generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.4 Snake Oil method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6 Author’s Pick 19
7 Hints 21
1
,Evan Chen (October 13, 2016) Summations
§1 Introduction
This is a handout about how to deal with complicated sums. Broadly, sums on olympiad
contests fall into a few different categories:
• Purely algebraic sums, like n n(n+1) 1
P
, which are mostly exercise in algebraic
manipulation. These are the kind you would get in a lecture named “sums and
products”.
• Sums which are combinatorial, involving expressions like nk . You would see this
in lectures named “combinatorial sums” and “counting in two ways”, or perhaps
“generating functions”.
• Sums which are Pnumber theoretic, involving functions like ϕ, µ, or which involve
expressions like d|n , or which ask you to take a sum modulo p. Often appears in
“multiplicative number theory”.
I think it is preferable to avoid separating the learning of these apparently disjoint topics,
hence the unified handout. There are some connected themes which underlie all three; in
particular, one of the big ideas which runs through the entire handout is the concept of
swapping the order of summation.
Theorem 1.1 (Swapping the order of summation)
Let f (a, b) be a function. Then
XX XX
f= f.
a∈A b∈B b∈B a∈A
This seemingly obvious fact is a nontrivial step in more than 50% of summation problems
(in the same way that cyclic quadrilaterals is used in more than 50% of geometry problems).
We will see this key idea again and again in the examples that follow. Thus any time
you see a double sum, you should always consider P computing the sum in the reversed
order. In fact, even if you only have a single you should consider rewriting the
expression as a double sum (e.g. a generating function) so that the above theorem applies.
You might also need to change the variables before this step; for example we also have
XX X X
f= f.
a≥0 b≥0 k≥0 a,b
a+b=k
§2 Algebraic manipulation
These are the most low-tech problems, and often appear on short-answer contests as a
result. These techniques apply to all sums, and especially to those which don’t have N or
C flavor.
Examples of things you can do:
• Look at telescoping sequences. The classic example that everyone knows of is
100
X 1
.
n(n + 1)
n=1
2
, Evan Chen (October 13, 2016) Summations
• Generalizing the above point, looking at partial fractions is very often a good
thing to do if your expression has polynomial denominators.
• Try to factor the expression. In particular, one can factor through double sums:
! !
XX X X
a2 (b + 1) = a2 (b + 1) .
a∈A b∈B a∈A b∈B
• Try swapping the order of summation. (This is so important we’re saying it
again.)
§2.1 Telescoping and partial fractions
I won’t provide too many examples here (though there are plenty in the practice problems!)
since this is a topic that often appears at the AIME level anyways. So here is my token
example.
Example 2.1 (Stanford 2011)
Evaluate the sum
X 7n + 32 3 n
· .
n(n + 2) 4
n≥1
Solution. Again, since we have a polynomial denominator, our first reflex is to decompose
its partial fractions. This gives us
7n + 32 16 9
= − .
n(n + 2) n n+2
Suddenly we’re done, because the sum telescopes according to the fact that 9 = (3/4)2 · 16:
X 16 3 n 16
n+2
3
− .
n 4 n+2 4
n≥1
We see the trailing terms in the sum tend to zero as n → ∞. So the answer is
16 3 16 9 9 33
1 · 4 + 2 · 16 = 12 + 2 = 2 .
§2.2 Swapping the order of summation
For a less contrived example, we now prove linearity of expectation, which is the key
result from [2].
The motivating example which I always present is that this allows one to compute the
expected number of fixed points in a random permutation of {1, . . . , n}:
Example 2.2
A random permutation of {1, . . . , n} has an average of one fixed point.
To see this, let’s look at the case n = 4:
3
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller modockochieng06. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
60281 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now