1 到 N 平方和公式推導與應用：數學歸納法證明及相關求和技巧

核心公式

平方和公式：

S₂(n) = 1² + 2² + ... + n² = n(n+1)(2n+1) / 6

數學歸納法證明

基礎步驟 (n=1)

左邊 = 1² = 1
右邊 = 1×2×3/6 = 1 ✓

歸納步驟

假設對 n=k 成立：S₂(k) = k(k+1)(2k+1)/6
證明 n=k+1 時成立：

S₂(k+1) = S₂(k) + (k+1)²
        = k(k+1)(2k+1)/6 + (k+1)²
        = (k+1)[k(2k+1) + 6(k+1)]/6
        = (k+1)[2k² + k + 6k + 6]/6
        = (k+1)(2k² + 7k + 6)/6
        = (k+1)(2k+3)(k+2)/6
        = (k+1)((k+1)+1)(2(k+1)+1)/6  ✓

故公式對所有正整數 n 成立。

相關求和變形技巧

連續整數乘積求和

Σ i(i+1) = Σ(i² + i) = S₂(n) + S₁(n)

其中 S₁(n) = n(n+1)/2，代入得：

Σ i(i+1) = n(n+1)(2n+1)/6 + n(n+1)/2
         = n(n+1)[(2n+1) + 3]/6
         = n(n+1)(2n+4)/6
         = n(n+1)(n+2)/3

通用套路：裂項相消

觀察 i(i+1)(i+2) 的差分：

i(i+1)(i+2) - (i-1)i(i+1) = i(i+1)[(i+2)-(i-1)] = 3i(i+1)
∴ i(i+1) = [i(i+1)(i+2) - (i-1)i(i+1)] / 3

求和時中間項相消：

Σ i(i+1) = [n(n+1)(n+2) - 0]/3 = n(n+1)(n+2)/3

同理可推導 Σ i(i+1)(i+2)、Σ i²(i+1) 等高階乘積和。

高階冪和公式速查 (Faulhaber 公式)

程序設計應用場景

1. 算法複雜度精確計算

// 雙層循環 i=1..n, j=i..n 總迭代次數
long long iterations = n*(n+1)/2; // S₁(n)

// 三層循環 i=1..n, j=i..n, k=j..n
long long iterations = n*(n+1)*(n+2)/6; // Σ S₁(i)

2. 競賽題目：HDU 4059 四次方和

S₄(n) = n⁵/5 + n⁴/2 + n³/3 - n/30
模運算下需計算模逆元：inv(2), inv(3), inv(5), inv(30)，或用矩陣快速冪避開分數。

3. 數學建模：離散積分近似

∫₀ⁿ x² dx ≈ Σ i² = n³/3 + n²/2 + n/6
誤差項 O(n)，大數據下相對誤差 O(1/n) 可忽略。

常見錯誤與避坑指南

1. 整數除法截斷：C++ 中 n*(n+1)*(2*n+1)/6 可能中間溢出或除法提前截斷。
   修正：1LL*n*(n+1)*(2*n+1)/6 或分步除以 2、3（利用連續整數必有偶數、3 的倍數）。
2. 公式記錯：分母 6 非 3，分子 2n+1 非 2n-1。背誦口訣：「一乘二乘二加一，除以六」
3. 忽略 long long：n=10⁵ 時平方和 ~10¹⁵ 超 int 範圍。

總結

平方和公式是離散數學基石，歸納法證明嚴謹優雅，裂項相消法更具普適性可推廣至高階乘積。工程上注意類型溢出、除法順序、模運算逆元處理。掌握 S₁, S₂, S₃ 三大基礎公式及裂項技巧，可解決 90% 競賽求和問題。