Тождество Кассини — тождество, утверждающее, что для -го числа Фибоначчи выполняется следующее соотношение:
.
Тождество Кассини было опубликовано астрономом Джованни Кассини в 1680 году, когда он был директором Парижской обсерватории. Позднее оно было доказано Робертом Симсоном в 1753 году. Однако это соотношение встречается уже у Иоганна Кеплера ещё в 1608 году.
В 1879 году бельгийский математик Эжен Каталан обобщил результат. Полученное соотношение известно как тождество Каталана:
.
Соотношение Кассини лежит в основе геометрической головоломки об исчезающей клетке, популяризованной Льюисом Кэрроллом и позднее Сэмом Лойдом. Суть задачи в том, чтобы разрезать шахматную доску на четыре части таким образом, чтобы затем составить из этих частей прямоугольник.
Аналогичная конструкция разбивает любой квадрат на четыре части с размерами сторон клеток. В результате получается прямоугольник , и в соответствии с тождеством Кассини одна клетка либо прибавляется, либо утрачивается, в зависимости от того, чётно или нечётно .
Для последовательностей чисел Люка тождество Кассини имеет вид:
, где .
Тождества типа Кассини последовательностей чисел Якобсталя и Якобсталя-Люка соответсвенно равны:
Доказательство тождества Кассини
Доказательство по индукции Докажем базу индукции для :
.
Таким образом, базовое утверждение выполняется.
Докажем переход: предположим для некоторого , выполняется равенство:
.
Докажем, что тогда утверждение выполняется и для :
Рассмотрим левую часть предположения. Прибавим и вычтем слагаемое :
.
Перегруппируем слагаемые, выделяя общие множители:
.
Используя реккурентное соотношение для чисел Фибоначчи: и , получаем:
Умножим обе части на :
.
Таким образом, из истинности утверждения для следует его истинность для .
Следовательно, согласно математической индукции, тождество выполняется для всех .
Доказательство с использованием матриц Элегантное доказательство тождества Кассини было предложено Д. Кнутом в 1994 году в известной работе «Искусство программирования»:
Докажем по индукции матричное тождество:
Докажем базу индукции при :
База индукции выполнена.
Положим, что утверждение верно для некоторого . Тогда:
Используя реккурентное соотношение для чисел Фибоначчи: и , получаем:
что соответствует утверждению при . Шаг индукции доказан.
Теперь вычислим определители обеих частей равенства:
Доказательство тождества Каталана По формуле Бине,
Подставляем:
Аналогично для :
Так как , и заметим, что ,
Так как
Следовательно, , что и требовалось доказать.
Литература
Примечания
Категория:Тождества Категория:Целочисленные последовательности