Lesson 2

Using generating functions, derive the formula \[1^{2}+2^{2}+\dotsb+n^{2}=\frac{n(n+1)(2n+1)}{6}\ .\] Knowing the formula, it is easy to prove it by induction. But what if we do not know it? With some intuition, one can guess that the result must be a cubic polynomial. Then, we can denote its coefficients as \(c_{0},c_{1},c_{2},c_{3}\), write linear equations for them from the values at \(n=0,1,2,3\). This method works (and for higher degrees too), though it does not provide guarantees. Below, we derive the formula using generating functions.