Problem 6: Sum Square Difference

Mathematical Development

Notation

Throughout, we write

Lemma 1 (Sum of the first $n$ natural numbers). For all $n \ge 1$,

Proof. By induction on $n$.

Base case: $S_1(1) = 1 = 1 \cdot 2 / 2$.

Inductive step: Assume $S_1(k) = k(k+1)/2$. Then

Alternative proof (Gauss’s pairing argument). Write the sum in two orders:

Adding termwise: $2S_1 = \sum_{i=1}^{n}(n+1) = n(n+1)$, so $S_1 = n(n+1)/2$. $\square$

Lemma 2 (Sum of squares). For all $n \ge 1$,

Proof. Consider the telescoping identity

Summing both sides for $k = 1, 2, \ldots, n$:

The left-hand side telescopes:

Substituting $S_1(n) = n(n+1)/2$ from Lemma 1:

Expanding $(n+1)^3 = n^3 + 3n^2 + 3n + 1$:

Combining over a common denominator:

where the last factorization follows from $2n^2 + 3n + 1 = (2n+1)(n+1)$ (verify: $(2n+1)(n+1) = 2n^2 + 3n + 1$).

Dividing by 3: $S_2(n) = \dfrac{n(n+1)(2n+1)}{6}$. $\square$

Theorem 1 (Closed form for the difference). For all $n \ge 1$,

Proof. By Lemmas 1 and 2,

Extracting the common factor $n(n+1)$:

Justification of the common denominator: $\frac{n^2(n+1)^2}{4} = \frac{3n^2(n+1)^2}{12}$ and $\frac{n(n+1)(2n+1)}{6} = \frac{2n(n+1)(2n+1)}{12}$.

Expanding the bracket:

We factor the quadratic $3n^2 - n - 2$. The discriminant is $\Delta = 1 + 24 = 25$, yielding roots

Therefore $3n^2 - n - 2 = 3\!\left(n - 1\right)\!\left(n + \tfrac{2}{3}\right) = (n-1)(3n+2)$.

Substituting:

Corollary 1 (Non-negativity). $D(n) \ge 0$ for all $n \ge 1$, with equality if and only if $n = 1$.

Proof. For $n \ge 2$, each factor $n, n-1, n+1, 3n+2$ is positive, so $D(n) > 0$. For $n = 1$: $D(1) = 1 \cdot 0 \cdot 2 \cdot 5 / 12 = 0$. $\square$

Theorem 2 (Combinatorial interpretation). The difference $D(n)$ counts twice the sum of all pairwise products:

Proof. By the multinomial expansion of a square,

This identity holds because $\left(\sum a_i\right)^2 = \sum_i a_i^2 + 2\sum_{i < j} a_i a_j$, which is verified by expanding $(a_1 + \cdots + a_n)(a_1 + \cdots + a_n)$ and separating diagonal terms ($i = j$) from off-diagonal terms ($i \ne j$), noting each unordered pair $\{i, j\}$ with $i \ne j$ contributes $a_i a_j + a_j a_i = 2a_i a_j$.

Subtracting $\sum i^2$ from both sides yields $D(n) = 2\sum_{i < j} ij$. $\square$

Remark. Theorem 2 makes the non-negativity of $D(n)$ transparent: it is a sum of products of positive integers.

Editorial

The implementation evaluates the closed formula derived above, so no enumeration is needed. Once $n$ is given, it substitutes $n$ into $D(n) = n(n-1)(n+1)(3n+2)/12$ and returns the result. This is sufficient because the algebraic reduction already transformed the original difference of sums into this polynomial expression.

Application to $n = 100$. We compute

Step by step:

• $100 \times 99 = 9{,}900$.
• $101 \times 302 = 30{,}502$.
• $9{,}900 \times 30{,}502 = 301{,}969{,}800$.
• $301{,}969{,}800 \div 12 = 25{,}164{,}150$.

Verification. $S_1(100) = 5{,}050$ and $S_1(100)^2 = 25{,}502{,}500$. Also $S_2(100) = 100 \times 101 \times 201 / 6 = 338{,}350$. Then $D(100) = 25{,}502{,}500 - 338{,}350 = 25{,}164{,}150$. $\checkmark$

Pseudocode

Algorithm: Difference Between Square of Sum and Sum of Squares
Require: An integer n ≥ 1.
Ensure: The value D = (∑_{k=1}^n k)^2 - ∑_{k=1}^n k^2.
1: Compute A ← n(n + 1) / 2.
2: Compute B ← n(n + 1)(2n + 1) / 6.
3: Set D ← A^2 - B.
4: Return D.

Complexity Analysis

Theorem 3 (Complexity). The closed-form algorithm computes $D(n)$ in $O(1)$ time and $O(1)$ space.

Proof. The formula $D(n) = n(n-1)(n+1)(3n+2)/12$ requires exactly 4 multiplications and 1 division, all on integers. No loops or data structures are needed. A brute-force approach computing $S_1(n)$ and $S_2(n)$ by iteration would require $O(n)$ time and $O(1)$ space. $\square$

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // D(n) = n(n-1)(n+1)(3n+2) / 12
    long long n = 100;
    long long ans = n * (n - 1) * (n + 1) * (3 * n + 2) / 12;
    cout << ans << endl;
    return 0;
}

"""Project Euler Problem 6: Sum Square Difference"""

def solve(n: int = 100) -> int:
    """D(n) = n(n-1)(n+1)(3n+2) / 12"""
    return n * (n - 1) * (n + 1) * (3 * n + 2) // 12

answer = solve()
assert answer == 25164150
print(answer)