Intuition The big pictureWe want closed formulas for the sums:
∑ k = 1 n 1 , ∑ k = 1 n k , ∑ k = 1 n k 2 , ∑ k = 1 n k 3 . \sum_{k=1}^{n}1,\qquad \sum_{k=1}^{n}k,\qquad \sum_{k=1}^{n}k^2,\qquad \sum_{k=1}^{n}k^3. ∑ k = 1 n 1 , ∑ k = 1 n k , ∑ k = 1 n k 2 , ∑ k = 1 n k 3 . WHY care? A sum with n n n n n n closed form lets you find the answer in one shot no matter how big n n n The master trick for all of these is the telescoping / difference method : pick a function f ( k ) f(k) f ( k ) f ( k + 1 ) − f ( k ) f(k+1)-f(k) f ( k + 1 ) − f ( k )
Definition Telescoping sumA sum ∑ k = 1 n ( f ( k + 1 ) − f ( k ) ) \displaystyle\sum_{k=1}^{n}\big(f(k+1)-f(k)\big) k = 1 ∑ n ( f ( k + 1 ) − f ( k ) ) collapses :
∑ k = 1 n ( f ( k + 1 ) − f ( k ) ) = f ( n + 1 ) − f ( 1 ) . \sum_{k=1}^{n}\big(f(k+1)-f(k)\big)=f(n+1)-f(1). ∑ k = 1 n ( f ( k + 1 ) − f ( k ) ) = f ( n + 1 ) − f ( 1 ) . WHY: write the terms out — ( f ( 2 ) − f ( 1 ) ) + ( f ( 3 ) − f ( 2 ) ) + ⋯ + ( f ( n + 1 ) − f ( n ) ) \big(f(2)-f(1)\big)+\big(f(3)-f(2)\big)+\dots+\big(f(n+1)-f(n)\big) ( f ( 2 ) − f ( 1 ) ) + ( f ( 3 ) − f ( 2 ) ) + ⋯ + ( f ( n + 1 ) − f ( n ) ) + + + − - −
We will now choose clever f ( k ) f(k) f ( k )
Intuition Gauss's pairing (dual coding — picture it)Write the sum forwards and backwards and stack:
S = 1 + 2 + ⋯ + ( n − 1 ) + n S = n + ( n − 1 ) + ⋯ + 2 + 1 \begin{aligned}S&=1+2+\dots+(n-1)+n\\ S&=n+(n-1)+\dots+2+1\end{aligned} S S = 1 + 2 + ⋯ + ( n − 1 ) + n = n + ( n − 1 ) + ⋯ + 2 + 1 ( n + 1 ) (n+1) ( n + 1 ) n n n 2 S = n ( n + 1 ) 2S=n(n+1) 2 S = n ( n + 1 )
Derivation from scratch — telescoping with f ( k ) = k 3 f(k)=k^3 f ( k ) = k 3
Why k 3 k^3 k 3 Because ( k + 1 ) 3 − k 3 (k+1)^3-k^3 ( k + 1 ) 3 − k 3 k 2 k^2 k 2
Worked example Full derivationStep 1. Expand the difference.
( k + 1 ) 3 − k 3 = 3 k 2 + 3 k + 1. (k+1)^3-k^3 = 3k^2+3k+1. ( k + 1 ) 3 − k 3 = 3 k 2 + 3 k + 1. Why this step? This links k 2 k^2 k 2 k k k 1 1 1
Step 2. Sum both sides k = 1 → n k=1\to n k = 1 → n ∑ k = 1 n [ ( k + 1 ) 3 − k 3 ] = ( n + 1 ) 3 − 1. \sum_{k=1}^n\big[(k+1)^3-k^3\big]=(n+1)^3-1. ∑ k = 1 n [ ( k + 1 ) 3 − k 3 ] = ( n + 1 ) 3 − 1. Why? Interior cubes cancel; only ends remain.
Step 3. RHS splits:
∑ ( 3 k 2 + 3 k + 1 ) = 3 ∑ k 2 + 3 ∑ k + ∑ 1. \sum(3k^2+3k+1)=3\sum k^2+3\sum k+\sum 1. ∑ ( 3 k 2 + 3 k + 1 ) = 3 ∑ k 2 + 3 ∑ k + ∑ 1. Why? Σ \Sigma Σ
Step 4. Substitute known results ∑ k = n ( n + 1 ) 2 \sum k=\frac{n(n+1)}{2} ∑ k = 2 n ( n + 1 ) ∑ 1 = n \sum 1=n ∑ 1 = n ( n + 1 ) 3 − 1 = 3 ∑ k 2 + 3 ⋅ n ( n + 1 ) 2 + n . (n+1)^3-1 = 3\sum k^2 + 3\cdot\frac{n(n+1)}{2}+n. ( n + 1 ) 3 − 1 = 3 ∑ k 2 + 3 ⋅ 2 n ( n + 1 ) + n .
Step 5. Solve for ∑ k 2 \sum k^2 ∑ k 2 ( n + 1 ) 3 − 1 = n 3 + 3 n 2 + 3 n . (n+1)^3-1 = n^3+3n^2+3n. ( n + 1 ) 3 − 1 = n 3 + 3 n 2 + 3 n . 3 ∑ k 2 = n 3 + 3 n 2 + 3 n − 3 n ( n + 1 ) 2 − n . 3\sum k^2 = n^3+3n^2+3n-\frac{3n(n+1)}{2}-n. 3 ∑ k 2 = n 3 + 3 n 2 + 3 n − 2 3 n ( n + 1 ) − n . n 3 + 3 n 2 + 2 n − 3 n 2 + 3 n 2 = 2 n 3 + 6 n 2 + 4 n − 3 n 2 − 3 n 2 = 2 n 3 + 3 n 2 + n 2 n^3+3n^2+2n-\frac{3n^2+3n}{2}=\frac{2n^3+6n^2+4n-3n^2-3n}{2}=\frac{2n^3+3n^2+n}{2} n 3 + 3 n 2 + 2 n − 2 3 n 2 + 3 n = 2 2 n 3 + 6 n 2 + 4 n − 3 n 2 − 3 n = 2 2 n 3 + 3 n 2 + n 2 n 3 + 3 n 2 + n = n ( 2 n 2 + 3 n + 1 ) = n ( n + 1 ) ( 2 n + 1 ) 2n^3+3n^2+n=n(2n^2+3n+1)=n(n+1)(2n+1) 2 n 3 + 3 n 2 + n = n ( 2 n 2 + 3 n + 1 ) = n ( n + 1 ) ( 2 n + 1 ) 3 ∑ k 2 = n ( n + 1 ) ( 2 n + 1 ) 2 ⇒ ∑ k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 . ✓ 3\sum k^2=\frac{n(n+1)(2n+1)}{2}\Rightarrow \sum k^2=\frac{n(n+1)(2n+1)}{6}. \checkmark 3 ∑ k 2 = 2 n ( n + 1 ) ( 2 n + 1 ) ⇒ ∑ k 2 = 6 n ( n + 1 ) ( 2 n + 1 ) . ✓
Derivation — telescoping with f ( k ) = k 4 f(k)=k^4 f ( k ) = k 4
Worked example Full derivationStep 1. ( k + 1 ) 4 − k 4 = 4 k 3 + 6 k 2 + 4 k + 1. (k+1)^4-k^4 = 4k^3+6k^2+4k+1. ( k + 1 ) 4 − k 4 = 4 k 3 + 6 k 2 + 4 k + 1. Why k 4 k^4 k 4 Its difference produces a k 3 k^3 k 3
Step 2. Sum k = 1 → n k=1\to n k = 1 → n ( n + 1 ) 4 − 1 (n+1)^4-1 ( n + 1 ) 4 − 1
Step 3. RHS = 4 ∑ k 3 + 6 ∑ k 2 + 4 ∑ k + n =4\sum k^3+6\sum k^2+4\sum k+n = 4 ∑ k 3 + 6 ∑ k 2 + 4 ∑ k + n
Step 4. Plug in the two known sums and solve:
4 ∑ k 3 = ( n + 1 ) 4 − 1 − 6 ⋅ n ( n + 1 ) ( 2 n + 1 ) 6 − 4 ⋅ n ( n + 1 ) 2 − n . 4\sum k^3=(n+1)^4-1-6\cdot\frac{n(n+1)(2n+1)}{6}-4\cdot\frac{n(n+1)}{2}-n. 4 ∑ k 3 = ( n + 1 ) 4 − 1 − 6 ⋅ 6 n ( n + 1 ) ( 2 n + 1 ) − 4 ⋅ 2 n ( n + 1 ) − n . n n n 4 ∑ k 3 = n 4 + 2 n 3 + n 2 = n 2 ( n + 1 ) 2 . 4\sum k^3 = n^4+2n^3+n^2 = n^2(n+1)^2. 4 ∑ k 3 = n 4 + 2 n 3 + n 2 = n 2 ( n + 1 ) 2 . ∑ k 3 = n 2 ( n + 1 ) 2 4 = [ n ( n + 1 ) 2 ] 2 . \sum k^3 = \dfrac{n^2(n+1)^2}{4}=\left[\dfrac{n(n+1)}{2}\right]^2. ∑ k 3 = 4 n 2 ( n + 1 ) 2 = [ 2 n ( n + 1 ) ] 2 .
Sum
Closed form
Leading behaviour
∑ 1 \sum 1 ∑ 1 n n n ∼ n \sim n ∼ n
∑ k \sum k ∑ k n ( n + 1 ) 2 \dfrac{n(n+1)}{2} 2 n ( n + 1 ) ∼ 1 2 n 2 \sim \tfrac12 n^2 ∼ 2 1 n 2
∑ k 2 \sum k^2 ∑ k 2 n ( n + 1 ) ( 2 n + 1 ) 6 \dfrac{n(n+1)(2n+1)}{6} 6 n ( n + 1 ) ( 2 n + 1 ) ∼ 1 3 n 3 \sim \tfrac13 n^3 ∼ 3 1 n 3
∑ k 3 \sum k^3 ∑ k 3 [ n ( n + 1 ) 2 ] 2 \left[\dfrac{n(n+1)}{2}\right]^2 [ 2 n ( n + 1 ) ] 2 ∼ 1 4 n 4 \sim \tfrac14 n^4 ∼ 4 1 n 4
Intuition 80/20 — the one pattern∑ k p ∼ n p + 1 p + 1 \sum k^p \sim \dfrac{n^{p+1}}{p+1} ∑ k p ∼ p + 1 n p + 1 exactly ∫ 0 n x p d x \int_0^n x^p\,dx ∫ 0 n x p d x
∑ k = 1 20 ( 3 k 2 − 2 k + 5 ) \sum_{k=1}^{20}(3k^2-2k+5) ∑ k = 1 20 ( 3 k 2 − 2 k + 5 ) Split (linearity): 3 ∑ k 2 − 2 ∑ k + 5 ∑ 1 3\sum k^2 - 2\sum k + 5\sum 1 3 ∑ k 2 − 2 ∑ k + 5 ∑ 1 Why? Break unknown big sum into known building blocks.
With n = 20 n=20 n = 20 ∑ k 2 = 20 ⋅ 21 ⋅ 41 6 = 2870 \sum k^2=\frac{20\cdot21\cdot41}{6}=2870 ∑ k 2 = 6 20 ⋅ 21 ⋅ 41 = 2870 ∑ k = 20 ⋅ 21 2 = 210 \sum k=\frac{20\cdot21}{2}=210 ∑ k = 2 20 ⋅ 21 = 210 ∑ 1 = 20 \sum 1=20 ∑ 1 = 20 = 3 ( 2870 ) − 2 ( 210 ) + 5 ( 20 ) = 8610 − 420 + 100 = 8290. =3(2870)-2(210)+5(20)=8610-420+100=\mathbf{8290}. = 3 ( 2870 ) − 2 ( 210 ) + 5 ( 20 ) = 8610 − 420 + 100 = 8290 .
Worked example Sum from a shifted start:∑ k = 5 12 k 2 \sum_{k=5}^{12}k^2 ∑ k = 5 12 k 2 Trick: ∑ k = 5 12 = ∑ k = 1 12 − ∑ k = 1 4 \sum_{k=5}^{12}=\sum_{k=1}^{12}-\sum_{k=1}^{4} ∑ k = 5 12 = ∑ k = 1 12 − ∑ k = 1 4 Why? Formulas start at k = 1 k=1 k = 1 = 12 ⋅ 13 ⋅ 25 6 − 4 ⋅ 5 ⋅ 9 6 = 650 − 30 = 620. =\frac{12\cdot13\cdot25}{6}-\frac{4\cdot5\cdot9}{6}=650-30=\mathbf{620}. = 6 12 ⋅ 13 ⋅ 25 − 6 4 ⋅ 5 ⋅ 9 = 650 − 30 = 620 .
Common mistake Steel-manning the classic slipsSlip 1: "∑ k 3 = ( ∑ k ) 2 \sum k^3 = (\sum k)^2 ∑ k 3 = ( ∑ k ) 2 ∑ k 2 = ( ∑ k ) ? \sum k^2=(\sum k)^{?} ∑ k 2 = ( ∑ k ) ? Why it feels right: the cube result is so pretty you expect a pattern. Fix: it's a coincidence unique to p = 3 p=3 p = 3 ∑ k 2 \sum k^2 ∑ k 2
Slip 2: Writing ∑ k = 1 n k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 \sum_{k=1}^{n}k^2 = \frac{n(n+1)(2n+1)}{6} ∑ k = 1 n k 2 = 6 n ( n + 1 ) ( 2 n + 1 ) shift when the sum starts at k ≠ 1 k\ne1 k = 1 Fix: use ∑ a b = ∑ 1 b − ∑ 1 a − 1 \sum_{a}^{b}=\sum_1^{b}-\sum_1^{a-1} ∑ a b = ∑ 1 b − ∑ 1 a − 1
Slip 3: Treating ∑ ( 3 k 2 ) \sum(3k^2) ∑ ( 3 k 2 ) ( ∑ 3 k ) 2 (\sum 3k)^2 ( ∑ 3 k ) 2 3 ( ∑ k ) 2 3(\sum k)^2 3 ( ∑ k ) 2 Fix: the constant pulls out linearly: ∑ 3 k 2 = 3 ∑ k 2 \sum 3k^2 = 3\sum k^2 ∑ 3 k 2 = 3 ∑ k 2
Recall Feynman: explain to a 12-year-oldImagine climbing stairs where each step is taller than the last. To find the total height you'd normally add every step. But there's a shortcut: line up two copies of the staircase — one going up, one flipped going down — and they form a perfect rectangle. Count the rectangle's squares, halve it, done. That's ∑ k \sum k ∑ k edges cancel out when stacked (telescoping), leaving only the top and bottom — and from that leftover we read off the total. So instead of adding a million things, we add just two.
Mnemonic Remember the four"One n, half-product, sixth-triple, square-the-triangle."
∑ 1 = n \sum1=n ∑ 1 = n ∑ k = n ( n + 1 ) 2 \sum k=\frac{n(n+1)}{2} ∑ k = 2 n ( n + 1 ) ∑ k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 \sum k^2=\frac{n(n+1)(2n+1)}{6} ∑ k 2 = 6 n ( n + 1 ) ( 2 n + 1 ) 2 n + 1 2n+1 2 n + 1 6 6 6 ∑ k 3 = ( ∑ k ) 2 \sum k^3=(\sum k)^2 ∑ k 3 = ( ∑ k ) 2
What is ∑ k = 1 n 1 \sum_{k=1}^n 1 ∑ k = 1 n 1 State ∑ k = 1 n k \sum_{k=1}^n k ∑ k = 1 n k n ( n + 1 ) 2 \dfrac{n(n+1)}{2} 2 n ( n + 1 ) State ∑ k = 1 n k 2 \sum_{k=1}^n k^2 ∑ k = 1 n k 2 n ( n + 1 ) ( 2 n + 1 ) 6 \dfrac{n(n+1)(2n+1)}{6} 6 n ( n + 1 ) ( 2 n + 1 ) State ∑ k = 1 n k 3 \sum_{k=1}^n k^3 ∑ k = 1 n k 3 [ n ( n + 1 ) 2 ] 2 \left[\dfrac{n(n+1)}{2}\right]^2 [ 2 n ( n + 1 ) ] 2 Which function's difference do you telescope to get ∑ k 2 \sum k^2 ∑ k 2 f ( k ) = k 3 f(k)=k^3 f ( k ) = k 3 , since
( k + 1 ) 3 − k 3 = 3 k 2 + 3 k + 1 (k+1)^3-k^3=3k^2+3k+1 ( k + 1 ) 3 − k 3 = 3 k 2 + 3 k + 1 Which function's difference gives ∑ k 3 \sum k^3 ∑ k 3 f ( k ) = k 4 f(k)=k^4 f ( k ) = k 4 , since
( k + 1 ) 4 − k 4 = 4 k 3 + 6 k 2 + 4 k + 1 (k+1)^4-k^4=4k^3+6k^2+4k+1 ( k + 1 ) 4 − k 4 = 4 k 3 + 6 k 2 + 4 k + 1 What does a telescoping sum ∑ k = 1 n [ f ( k + 1 ) − f ( k ) ] \sum_{k=1}^n[f(k+1)-f(k)] ∑ k = 1 n [ f ( k + 1 ) − f ( k )] f ( n + 1 ) − f ( 1 ) f(n+1)-f(1) f ( n + 1 ) − f ( 1 ) ∑ k 3 \sum k^3 ∑ k 3 ∑ k \sum k ∑ k (the triangular number)
How do you evaluate ∑ k = 5 12 k 2 \sum_{k=5}^{12}k^2 ∑ k = 5 12 k 2 ∑ 1 12 − ∑ 1 4 = 650 − 30 = 620 \sum_{1}^{12}-\sum_{1}^{4}=650-30=620 ∑ 1 12 − ∑ 1 4 = 650 − 30 = 620 Approximate size of ∑ k p \sum k^p ∑ k p n n n n p + 1 p + 1 \dfrac{n^{p+1}}{p+1} p + 1 n p + 1 (matches
∫ 0 n x p d x \int_0^n x^p dx ∫ 0 n x p d x )
Evaluate ∑ k = 1 20 ( 3 k 2 − 2 k + 5 ) \sum_{k=1}^{20}(3k^2-2k+5) ∑ k = 1 20 ( 3 k 2 − 2 k + 5 )
Telescoping Series — the core cancellation trick used in every proof here.Arithmetic Progressions — ∑ k \sum k ∑ k a = 1 , d = 1 a=1,d=1 a = 1 , d = 1 Mathematical Induction — alternative proof method for each formula.Definite Integrals as Limits of Sums — Riemann sums use ∑ k , ∑ k 2 \sum k, \sum k^2 ∑ k , ∑ k 2 Binomial Theorem — expands ( k + 1 ) p (k+1)^p ( k + 1 ) p Triangular Numbers — ∑ k \sum k ∑ k ∑ k 3 = ( triangular ) 2 \sum k^3=(\text{triangular})^2 ∑ k 3 = ( triangular ) 2
expand k+1 cubed minus k cubed
Intuition Hinglish mein samjhoDekho, idea simple hai: hume chahiye ek short-cut formula taaki 1 + 2 + ⋯ + n 1+2+\dots+n 1 + 2 + ⋯ + n 1 2 + 2 2 + ⋯ + n 2 1^2+2^2+\dots+n^2 1 2 + 2 2 + ⋯ + n 2 n n n
Sabse pyaara trick hai telescoping . Iska matlab: aisa function f ( k ) f(k) f ( k ) f ( k + 1 ) − f ( k ) f(k+1)-f(k) f ( k + 1 ) − f ( k ) + + + − - − ∑ k \sum k ∑ k f ( k ) = k 2 f(k)=k^2 f ( k ) = k 2 ∑ k 2 \sum k^2 ∑ k 2 f ( k ) = k 3 f(k)=k^3 f ( k ) = k 3 ∑ k 3 \sum k^3 ∑ k 3 f ( k ) = k 4 f(k)=k^4 f ( k ) = k 4
Ek zabardast baat yaad rakhna: ∑ k 3 = ( ∑ k ) 2 \sum k^3 = (\sum k)^2 ∑ k 3 = ( ∑ k ) 2 square hota hai. Yeh coincidence sirf cube ke saath hai, isko squares pe mat generalize karna
(common galti!). Aur agar sum k = 1 k=1 k = 1 ∑ 5 12 = ∑ 1 12 − ∑ 1 4 \sum_{5}^{12} = \sum_{1}^{12}-\sum_{1}^{4} ∑ 5 12 = ∑ 1 12 − ∑ 1 4 ∑ k p ≈ n p + 1 p + 1 \sum k^p \approx \frac{n^{p+1}}{p+1} ∑ k p ≈ p + 1 n p + 1
