Practice with manipulating sums, and in particular switching the order of summation (or integration). Features generating functions and Snake Oil as well. The Gen Func unit is an optional prerequisite.
Quick List
ROUF = Roots of unity filter
Reading
- Public summations handout
- If you'd like, this 3B1B: https://www.youtube.com/watch?v=bOXCLR3Wric&t=15s
- it's the best GenFunc/ROUF intro!
Topics Covered
- Expected value, sum swapping, and double counting
- Generating functions and the snake oil method
- Telescoping
- If you're taking Multivariable, variable order swapping
- ROUF
Blurb
This unit is an introduction to standard summations in olympiads. Summations involved are not just algebraic, but also number theoretic and combinatorial. Core techniques such as swapping the order of summation, telescoping, expected value, roots of unity filter, multiplicity, Dirchlet convolution, generating functions, and snake oil are all taught in the prerequisite material; Evan Chen's public summations handout. The unit examples are more nuanced, involving clever combinations of the methods already taught. The problems aren't too difficult, but they will provide a challenge, especially to those who are new to the snake oil method.
Notable Problems
Putnam 2015 B4: Standard geometric series taken to the max level.
USAMO 2010 5: Nontrivial number theoretic summation.
IMO 1995 6: Classic problem, very satisfying.
2021 SL A2: Hardest in the B level set, modern summation problem.
18.02 Integral Swapping: Get your calculus hat on! We're swapping integrals today.