오늘 학교에서 갑자기 문득 든 생각이다.

어떠한 수열의 제곱의 합은 계산하기 빡세니까, 수열의 합의 제곱으로 바꾸어 계산하는 법이 없을까?

노트에 즉시 식을 써내려갔다.

2. 5개 항으로 유도해보기

$$(x_1+x_2+x_3+x_4+x_5)^2=(x_1+x_2+x_3+x_4+x_5)(x_1+x_2+x_3+x_4+x_5)$$ $$=x_1x_1+x_2x_2+x_3x_3+x_4x_4+x_5x_5+2(x_1x_2+x_1x_3+x_1x_4+x_1x_5+x_2x_3+x_2x_4+x_2x_5+x_3x_4+x_3x_5+x_4x_5)\$$ $$2(x_1x_2+x_1x_3+x_1x_4+x_1x_5+x_2x_3+x_2x_4+x_2x_5+x_3x_4+x_3x_5+x_4x_5)$$ $$=2{x_1(x_2+x_3+x_4+x_5)+x_2(x_3+x_4+x_5)+x_3(x_4+x_5)+x_4(x_5)}$$

아 제곱의 합을 합의 제곱의 형태로 고치려면, 교차항의 합을 써야하구나. 어라? 이거 누적합이잖아.

$$S_1 = x_1$$ $$S_2 = S_1 + x_2$$ $$S_3 = S_2 + x_3\\vdots$$ $$S_5 = S_4+x_5\$$ $$2{x_1(x_2+x_3+x_4+x_5)+x_2(x_3+x_4+x_5)+x_3(x_4+x_5)+x_4(x_5)}$$ $$=2{x_1(S_5-S_1)+x_2(S_5-S_2)+x_3(S_5-S_3)+x_4(S_5-S_4)}$$ $$=2\sum\limits_{k=1}^{4}{x_k(S_5-S_k)}$$

이제 수식을 정리하여 완성해볼까?

$$(x_1^2+x_2^2+x_3^2+x_4^2+x_5^2)=(x_1+x_2+x_3+x_4+x_5)^2-2\sum\limits_{k=1}^{4}{x_k(S_5-S_k)}$$

3. 일반화

$$X=(x_k){k=1}^n\quad n=|X|\$$ $$S_n = S{n-1}+x_n$$ $$\sum\limits_{k=1}^n{x_k^2}=(\sum\limits_{k=1}^n{x_k})^2-2\sum\limits_{k=1}^{n-1}{x_k(S_n-S_k)}$$

4. 증명

$$S_n-S_k=\sum\limits_{i=1}^{n}{x_i}-\sum\limits_{i=1}^{k}{x_i}=\sum\limits_{i=k+1}^{n}{x_i}\$$ $$\sum\limits_{k=1}^{n-1}{x_k(S_n-S_k)}=\sum\limits_{k=1}^{n-1}{x_k\cdot\sum\limits_{i=k+1}^{n}{x_i}}=\sum\limits_{1\le k<i\le n}{x_kx_i}\$$ $$\sum\limits_{k=1}^{n}{x_k^2}=(\sum\limits_{k=1}^{n}{x_k})^2-2\sum\limits_{1\le k<i\le n}{x_kx_i}$$ $$=(\sum\limits_{k=1}^{n}{x_k})^2-2\sum\limits_{k=1}^{n-1}{x_k(S_n-S_k)}\quad\text{Q.E.D.}$$

5. 코드 구현 및 검증

파이썬

X = list(map(int, input().split(" "))); n = len(X)
S = [0] * n; S[0] = X[0]
for i in range(1, n): S[i] = S[i-1] + X[i]

a = sum(x**2 for x in X)
b = (S[n-1] ** 2) - (2 * sum( X[k] * (S[n-1] - S[k]) for k in range(n-1)))

print(f"original : {a}")
print(f"zephyr's method : {b}")

C++

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N;
    cin >> N;

    vector<int> X(N);
    for (int i = 0; i < N; i++)
        cin >> X[i];

    vector<int> S(N); S[0] = X[0];
    for (int i = 1; i < N; i++)
        S[i] = S[i - 1] + X[i];

    int a = 0, b = 0;
    for (int i = 0; i < N; i++)
        a += X[i] * X[i];

    b = S[N - 1] * S[N - 1];
    for (int k = 0; k < N - 1; k++)
        b -= 2 * X[k] * (S[N-1] - S[k]);

    cout << "original :" << a << endl;
    cout << "zephyr's method :" << b;
}

$\[0.5em]$

6. 마치며

학교에서 문득 든 생각으로 시작해서, 단순 수식 전개부터 누적합을 이용한 일반화 및 수학적 증명까지 완성해 보았다. 알고리즘 공부를 하며 배웠던 누적합이 여기서 쓰일 줄은 몰랐다. 내가 스스로 고민하여 도출해낸 첫 공식이라 뿌듯하다!