Тут вже є щось цікаве :)
Ось всі сторінки:
Нехай, ми хочемо знайти таке f(n), щоб:
f(n) = 1^2 + 2^2 + 3^2 + ... + n^2.
Для того щоб спростити завдання, визначимо два власивості f(n):
1. f(n) - f(n - 1) = (1^2 + 2^2 + ... + (n - 1)^2 + n^2) - (1^2 + 2^2 + ... + (n - 1)^2) = n^2.
2. f(0) = 0.
Ці два умови достатні, щоб f(n) був правильною формулою. Чому? Ось приклад для f(3):
f(3) = 3^2 + f(2) = 3^2 + 2^2 + f(1) = 3^2 + 2^2 + 1^2 + f(0) = 3^2 + 2^2 + 1^2.
Така формула називається РЕКУРСИВНОЮ.
Тепер попробуємо підставити f(n) = n^3. Можливо, щось вийде?
Перевіряємо першу умову: f(n) - f(n - 1) = n^3 - (n - 1)^3 = 3n^2 - 3n + 1.
Це вже близько, але ми би хтіли, щоб квадратний член многочлена був рівний 1.
Тому попробуємо f(n) = n^3/3: f(n) - f(n - 1) = (n^3 - (n - 1)^3)/3 = n^2 - n + 1/3.
Тепер у нас є проблема: ще є зайві - n + 1/3. Тому попробуємо додати ще щось до f(n), щоб це скоротити.
Попробуємо дізнатися, що станеться, якщо f(n) = n^2: f(n) - f(n - 1) = (n^2 - (n - 1)^2) = 2n - 1.
Це дуже близько, але нам треба додати n - 1/3, а не 2n - 1. Тому попробуємо n^2/2:
f(n) - f(n - 1) = (n^2 - (n - 1)^2) = n - 1/2.
Це дуже класно, адже (n^2 - n + 1/3) + (n - 1/2) = n^2 - 1/6. Це дуже близько.
Тому підставимо f(n) = n^3/3 + n^2/2: f(n) - f(n - 1) = (n^3/3 + n^2/2 - ((n - 1)^3/3 + (n - 1)^2/2)) = (n^3/3 - (n - 1)^3/3) + (n^2/2 - (n - 1)^2/2) = ... = n^2 - 1/6.
Лише залишилося -1/6 вбити. Тому підставимо f(n) = n: f(n) - f(n - 1) = n - (n - 1) = 1. Тобто, якщо f(n) = n/6, то f(n) - f(n - 1) = n/6 - (n - 1)/6 = (n - (n - 1))/6 = 1/6.
Тобто, теоретично, фінальною формулою є:
f(n) = n^3/3 + n^2/2 + n/6
Або, якщо вивести 6 як спільний знаменник:
f(n) = (2n^3 + 3n^2 + n)/6
Перевіримо обидва властивості:
f(n) - f(n - 1) = (2n^3 + 3n^2 + n)/6 - (2(n - 1)^3 + 3(n - 1)^2 + (n - 1))/6 = (2n^3 + 3n^2 + n - 2(n - 1)^3 - 3(n - 1)^3 - (n - 1)/6 = (2n^3 + 3n^2 + n - 2n^3 + 6n^2 - 6n + 2 - 3n^2 + 6n - 3 - n + 1)/6 = (6n^2)/6 = n^2.
f(0) = (2*0^3 + 3*0^2 + 0)/6 = 0.
Отже, це і є повною формулою!