計算 1 * 2 + 2 * 3 +...+ (N - 1) * N 總和

題目

計算 1 * 2 + 2 * 3 +…+ (n-1) * n 總和。
Write a function to calculate 1 * 2 + 2 * 3 + … + (N - 1) * N.

題目為計算 1 * 2 + 2 * 3 +…+ (n-1) * n 的總和，一樣是求合的問題，同樣使用迴圈或遞迴即可，如果能用數學證明出公式的話，也可以直接套公式。

int sum(int n)
{
    int sum = 0;
    for (int i = 2; i <= n; ++i)
        sum += (i - 1) * i;
    return sum;
}

int sum(int n)
{
    if (n < 2)
        return 0;
    return (n - 1) * n + sum(n - 1);
}

網路上沒有找到比較好的推導，主要概念是將數列拆解為下面兩個數列

然後這兩個數列可以找到公式

最後將兩個式子相減

寫成程式碼

int sum(int n)
{
    return (n - 1) * n * (n + 1) / 3;
}