Сегодня наткнулся на статью о скругленных прямоугольниках в дизайне макинтошей. Смысл статьи не главное. Удивило другое, не знал о таком свойстве чисел. Фрагмент из статьи:
Способ Билла использовал тот факт, что сумма последовательных нечетных чисел всегда является следующим полным квадратом (например, 1 + 3 = 4, 1 + 3 + 5 = 9, 1 + 3 + 5 + 7 = 16 и так далее).
Интересно, как называется данное свойство? И как это доказывается? Ведь наверняка, если такое свойство использовали в разработке алгоритмов значит оно должно действовать в 100% случаев.
Выглядит обалденно, а мат.индукцией доказывается элементарно 🙂
Базу вы уже написали
Пускай для k правило доказано: 1 + .. + (2k-1) = k^2
Докажем для k+1:
1 + .. + (2k-1) + (2k+1) = k^2 + (2k + 1) = (k+1)^2
Матиндукция — лучшее доказательство, но мне очень нравится показывать этот факт
графически. Заметил это свойство квадратов, когда рассматривал квадратную кафельную
плитку в бассейне в детстве.
Имеем квадратную плитку.
Очевидно, 1^2 = 1.
Теперь, добавим к этому квадрату еще 3 квадрата (сверху, справа и по диагонали
сверху-справа). Получаем 1 + 3 = 4.
В общем случае, на каждом шаге имеем большой квадрат, состоящий из k квадратиков по
стороне. Прибавляем k квадратиков сверху, k квадратиков справа и еще один по диагонали.
Таким образом, на каждом ходу мы добавляем 2k+1 квадратик, чтобы дополнить
имеющийся большой квадрат k*k до квадрата (k+1)*(k+1)
Да, Дональд Кнут посвятил в своем 3х томнике целую главу на эту тему.
К черту индукцию =)
Еще проще: у нас арифметическая прогрессия вида: ak=2k-1, ее сумма (1+2*n-1)*n/2=n^2
P.S. формула суммы: ((a1+an)*n)/2
с квадратной плиткой — это интересно.
(n+1)^2-n^2=2n+1. Полагая n=0 и далее получим последовательные нечетные числа.
katmoon, спасибо! Даже не подумал об индукции!