Note này được dựa trên Concrete Mathematics, 2.5

Ta xét bài toán tính ~\square_n = \sum_{0 \leq k \leq n} k^2~

0. OEIS

Ta có thể tính các giá trị ~\square_n~ với ~n = 0, 1, 2, 3, 4, 5~, rồi sử dụng trang oeis.org để tra công thức.

1. Đoán công thức, chứng minh bằng quy nạp

Đây là phương pháp cơ bản trong sách giáo khoa, tuy nhiên vấn đề chính là các bạn cần biết cách đoán.

2. Pertubation method

Ta sẽ thử áp dụng pertubation method để tính ~\square_n~

Ta có:

~\square_{n+1} = \square_n + (n+1)^2~

~\square_{n+1} = 0 + \sum_{1 \leq k \leq n+1} k^2 = \sum_{1 \leq k+1 \leq n+1} (k+1)^2 = \sum_{0 \leq k \leq n} (k^2 + 2k + 1) = \square_n + 2\sum_{0 \leq k \leq n} k + \sum_{0 \leq k \leq n} 1 = \square_n + 2\sum_{0 \leq k \leq n} k + n+1~

Do đó, ~\square_n + (n+1)^2 = \square_n + 2\sum_{0 \leq k \leq n} k + n+1 \Rightarrow 2\sum_{0 \leq k \leq n} k = (n+1)^2 - (n+1)~

~\square_n~ biến mất nên phương án này thất bại.

Tuy nhiên, ta có thể để ý thấy là ta có thể thu được công thức cho ~\sum_{0 \leq k \leq n} k~ tử việc áp dụng pertubation method cho ~\square_n~. Vì thế, ta có ý tưởng áp dụng pertubation method cho ~C_n = \sum_{0 \leq k \leq n} k^3~ để ra được công thức của ~\square_n~

Ta có:

~C_{n+1} = C_n + (n+1)^3~

~C_{n+1} = 0 + \sum_{1 \leq k \leq n+1} k^3 = \sum_{1 \leq k+1 \leq n+1} (k+1)^3 = \sum_{0 \leq k \leq n} (k^3 + 3k^2 + 3k + 1) = C_n + 3\square_n + 3\frac{n(n+1)}{2} + (n+1)~

Do đó ~C_n + (n+1)^3 = C_n + 3\square_n + 3\frac{n(n+1)}{2} + (n+1) \Rightarrow \boxed{\square_n = \frac{(n+1)^3 - 3\frac{n(n+1)}{2} - (n+1)}{3} = \frac{n(n+1)(2n+1)}{6}}~

3. Repertoire method

Chúng ta sẽ thử tìm công thức tổng quát cho công thức truy hồi sau:

~R_0 = \alpha~

~R_n = R_{n-1} + \beta + \gamma n + \delta n^2~

Đặt ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~

Giả sử ~R_n = 1~. Khi đó ~\begin{cases} \alpha = 1 \\ 1 = 1 + \beta + \gamma n + \delta n^2 \Rightarrow \beta + \gamma n + \delta n^2 = 0 + 0n + 0n^2 \end{cases} \Rightarrow \alpha = 1, \beta = 0, \gamma = 0, \delta = 0~.

Thế vào ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~, ta có ~\boxed{A(n) = 1}~

Giả sử ~R_n = n~. Khi đó ~\begin{cases} \alpha = 0 \\ n = (n-1) + \beta + \gamma n + \delta n^2 \end{cases} \Rightarrow \alpha = 0, \beta = 1, \gamma = 0, \delta = 0~.

Thế vào ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~, ta có ~\boxed{B(n) = n}~

Giả sử ~R_n = n^2~. Khi đó ~\begin{cases} \alpha = 0 \\ n^2 = (n-1)^2 + \beta + \gamma n + \delta n^2 \end{cases} \Rightarrow \alpha = 0, \beta = -1, \gamma = 2, \delta = 0~.

Thế vào ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~, ta có ~2C(n) - B(n) = n^2 \Rightarrow \boxed{C(n) = \frac{n^2 + n}{2}}~

Giả sử ~R_n = n^3~. Khi đó ~\begin{cases} \alpha = 0 \\ n^3 = (n-1)^3 + \beta + \gamma n + \delta n^2 \end{cases} \Rightarrow \alpha = 0, \beta = 1, \gamma = -3, \delta = 3~.

Thế vào ~R_n = A(n)\alpha + B(n) \beta + C(n) \gamma + D(n) \delta~, ta có ~3D(n) - 3C(n) + B(n) = n^3 \Rightarrow \boxed{D(n) = \frac{n^3 + 3\frac{n^2 + n}{2} - n}{3} = \frac{n(n+1)(2n+1)}{6}}~

Ta có:

~\square_0 = 0~

~\square_n = \square_{n-1} + n^2~

nên ta áp dụng công thức khi ~\alpha = 0, \beta = 0, \gamma = 0, \delta = 1~. Tức ~\square_n = D(n) = \boxed{\frac{n(n+1)(2n+1)}{6}}~

4. Dùng sai số giữa ~\int~ và ~\sum~

Ta thấy ~\int~ và ~\sum~ là hai kí hiệu có điểm liên quan chặt chẽ với nhau. Trong khi ~\int~ có thể dùng để tính phần diện tích nằm dưới đường cong thì ~\sum~ có thể được dùng để tính xấp xỉ diện tích nằm dưới đường cong bằng cách tính tổng diện tích các hình chữ nhật.

Từ mối quan hệ giữa ~\int~ và ~\sum~ mà ta có ý tưởng tính ~E_n = \sum_{k=0}^n f(k) - \int_0^n f(x)dx~, biết đâu ta ra được công thức cho ~E_n~ và ~\int_0^n f(x)dx~ mà nhờ đó ra được công thức cho ~\sum_{k=0}^n f(k)~

Ví dụ:

~E_n = \sum_{k=0}^n k^2 - \int_0^n x^2 dx = \sum_{k=0}^n k^2 - (\int_0^1 x^2 dx + \int_1^2 x^2 dx + ... + \int_{n-1}^n x^2dx)~

~E_n = \sum_{k=1}^n (k^2 - \int_{k-1}^k x^2 dx)~

~E_n = \sum_{k=1}^n (k^2 - [\frac{x^3}{3}]_{k-1}^k)~

~E_n = \sum_{k=1}^n (k^2 - \frac{k^3 - (k-1)^3}{3}) = \sum_{k=1}^n(k - \frac{1}{3})~

Từ đây ta dễ dàng tính được ~E_n~. Việc tính ~\int_0^n x^2 dx~ cũng đơn giản, và từ hai biểu thức này và công thức ~E_n = \sum_{k=0}^n f(k) - \int_0^n f(x)dx~, ta tính được ~\square_n~

5. Biến tổng một biến thành tổng nhiều biến

Ta có:

~\square_n = \sum_{k=1}^n k^2 = \sum_{k=1}^n \underbrace{k+k+k+...+k}_{k \text{ lần}} = \sum_{k=1}^n \sum_{j=1}^k k~

Ta sẽ tìm cách mang ~\sum_j~ ra ngoài. Xét các cặp ~(k,j)~ được xét trong tổng. Các cặp này thỏa mãn điều kiện ~1 \leq j \leq k \leq n~.

~j~ có thể chạy từ ~1~ đến ~n~, và với mỗi ~j~, ~k~ có thể chạy từ ~j~ đến ~n~. Vì vậy:

~\square_n = \sum_{j=1}^n \sum_{k=j}^n k~

~\square_n = \sum_{j=1}^n \frac{(j + n)(n - j + 1)}{2}~ (dùng công thức tính tổng ~j + (j+1) + ... + n~)

~\square_n = \frac{1}{2} \sum_{j=1}^n (-j^2 + j + n^2 + n)~

~\square_n = -\frac{1}{2}\square_n + \frac{1}{2}(\frac{n(n+1)}{2} + n^3 + n^2)~

~\Rightarrow \frac{3}{2}\square_n = \frac{n(n+1)}{2} + n^3 + n^2~

Từ đây, ta dễ dàng tính được ~\square_n~

Ngoài các phương pháp trên, chúng ta còn hai phương pháp sử dụng sai phân (note sau), hoặc sử dụng hàm sinh.