TAOCP 1.2.6 Exercise 14

Exercise 14. [M21] Evaluate $\sum_{k=0}^{n} k^4$.

Verified: yes
Solve time: 29s

Solution

We seek a closed form for the sum

$$ \sum_{k=0}^{n} k^4. $$

By the argument in Section 1.2.6.E, any power $k^m$ can be expressed as a linear combination of binomial coefficients $\binom{k}{j}$ with $0 \le j \le m$. We first determine the coefficients for $k^4$.

We look for constants $c_0, c_1, c_2, c_3, c_4$ such that

$$ k^4 = c_0 \binom{k}{0} + c_1 \binom{k}{1} + c_2 \binom{k}{2} + c_3 \binom{k}{3} + c_4 \binom{k}{4}. $$

Compute the expansions of $\binom{k}{j}$ in powers of $k$:

$$ \begin{aligned} \binom{k}{0} &= 1,\ \binom{k}{1} &= k,\ \binom{k}{2} &= \frac{k(k-1)}{2} = \frac{k^2 - k}{2},\ \binom{k}{3} &= \frac{k(k-1)(k-2)}{6} = \frac{k^3 - 3k^2 + 2k}{6},\ \binom{k}{4} &= \frac{k(k-1)(k-2)(k-3)}{24} = \frac{k^4 - 6k^3 + 11k^2 - 6k}{24}. \end{aligned} $$

Now equate coefficients of powers of $k$:

Coefficient of $k^4$: only $\binom{k}{4}$ contributes. Therefore

$$ c_4 \cdot \frac{1}{24} = 1 \implies c_4 = 24. $$

Coefficient of $k^3$: $\binom{k}{3}$ contributes $\frac{1}{6}c_3$, $\binom{k}{4}$ contributes $- \frac{6}{24} c_4 = -\frac{1}{4}\cdot 24 = -6$. We require the sum to be zero (no $k^3$ term in $k^4$):

$$ \frac{1}{6} c_3 - 6 = 0 \implies c_3 = 36. $$

Coefficient of $k^2$: $\binom{k}{2}$ contributes $\frac{1}{2}c_2$, $\binom{k}{3}$ contributes $-\frac{3}{6}c_3 = -\frac{1}{2} \cdot 36 = -18$, $\binom{k}{4}$ contributes $\frac{11}{24} c_4 = \frac{11}{24}\cdot 24 = 11$. Sum must be $0$:

$$ \frac{1}{2} c_2 - 18 + 11 = 0 \implies \frac{1}{2} c_2 - 7 = 0 \implies c_2 = 14. $$

Coefficient of $k^1$: $\binom{k}{1}$ contributes $c_1$, $\binom{k}{2}$ contributes $-\frac{1}{2}c_2 = -7$, $\binom{k}{3}$ contributes $\frac{2}{6}c_3 = \frac{1}{3}\cdot 36 = 12$, $\binom{k}{4}$ contributes $-\frac{6}{24} c_4 = -6$. Sum must be $0$:

$$ c_1 - 7 + 12 - 6 = 0 \implies c_1 -1 =0 \implies c_1 =1. $$

Coefficient of $k^0$: $\binom{k}{0}$ contributes $c_0$, all others contribute $0$. Sum must be $0$:

$$ c_0 = 0. $$

Thus we have the decomposition

$$ k^4 = \binom{k}{1} + 14 \binom{k}{2} + 36 \binom{k}{3} + 24 \binom{k}{4}. $$

By repeated application of Eq. (11), the sums of binomial coefficients are:

$$ \sum_{k=0}^{n} \binom{k}{j} = \binom{n+1}{j+1}. $$

Hence

$$ \sum_{k=0}^{n} k^4 = \sum_{k=0}^{n} \binom{k}{1} + 14 \sum_{k=0}^{n} \binom{k}{2} + 36 \sum_{k=0}^{n} \binom{k}{3} + 24 \sum_{k=0}^{n} \binom{k}{4} = \binom{n+1}{2} + 14 \binom{n+1}{3} + 36 \binom{n+1}{4} + 24 \binom{n+1}{5}. $$

Expanding in factorials using Eq. (5):

$$ \begin{aligned} \binom{n+1}{2} &= \frac{(n+1)n}{2},\ \binom{n+1}{3} &= \frac{(n+1)n(n-1)}{6},\ \binom{n+1}{4} &= \frac{(n+1)n(n-1)(n-2)}{24},\ \binom{n+1}{5} &= \frac{(n+1)n(n-1)(n-2)(n-3)}{120}. \end{aligned} $$

Compute the linear combination:

$$ \begin{aligned} \sum_{k=0}^{n} k^4 &= \frac{(n+1)n}{2} + 14 \cdot \frac{(n+1)n(n-1)}{6} + 36 \cdot \frac{(n+1)n(n-1)(n-2)}{24} + 24 \cdot \frac{(n+1)n(n-1)(n-2)(n-3)}{120} \ &= \frac{(n+1)n}{2} + \frac{7(n+1)n(n-1)}{3} + \frac{3(n+1)n(n-1)(n-2)}{2} + \frac{(n+1)n(n-1)(n-2)(n-3)}{5}. \end{aligned} $$

Factoring $(n+1)n$:

$$ \sum_{k=0}^{n} k^4 = (n+1)n \left[ \frac{1}{2} + \frac{7(n-1)}{3} + \frac{3(n-1)(n-2)}{2} + \frac{(n-1)(n-2)(n-3)}{5} \right]. $$

Combining terms over common denominator $30$:

$$ \frac{15 + 70(n-1) + 45(n-1)(n-2) + 6(n-1)(n-2)(n-3)}{30}. $$

Simplifying the numerator:

$$ \begin{aligned} 15 + 70(n-1) &= 15 + 70n - 70 = 70n - 55,\ 70n - 55 + 45(n-1)(n-2) &= 70n -55 + 45(n^2 - 3n + 2) = 70n - 55 + 45n^2 -135n +90 = 45n^2 -65n +35,\ 45n^2 -65n +35 + 6(n-1)(n-2)(n-3) &= 45n^2 -65n +35 +6(n^3 -6n^2 +11n -6) = 6n^3 + 9n^2 +1n -1. \end{aligned} $$

Check: $6n^3 +9n^2 + n -1$. Divide by 30:

$$ \sum_{k=0}^{n} k^4 = \frac{6n^3 +9n^2 + n -1}{30} (n+1)n \quad \text{or better factor as standard formula}. $$

It is standard to write

$$ \sum_{k=0}^{n} k^4 = \frac{n(n+1)(2n+1)(3n^2 + 3n -1)}{30}. $$

Verification: Expand $(n)(n+1)(2n+1)(3n^2 +3n -1)/30$:

$$ (n)(n+1) = n^2 + n,\quad (2n+1)(3n^2 +3n -1) = 6n^3 +6n^2 -2n +3n^2 +3n -1 = 6n^3 +9n^2 + n -1, $$

matching the previous numerator. Therefore the formula is correct.

Final answer: