Последовательность Падована: формула и примеры

Последовательность Падована получается из трёх единиц по правилу, похожему на правило Фибоначчи, но с важным отличием: для следующего числа складывают не два соседних члена, а члены на два и три шага назад. Первые значения таковы: . Из этого простого правила возникает пластическое число: к нему стремятся отношения соседних членов. В калькуляторе можно выбрать номер и проверить оба слагаемых, прежде чем разбирать формулы.
Определение и первые члены
Зафиксируем нумерацию с нуля и начальные условия:
Рекуррентная формула задаёт новый член через уже известные. Например, , а . Повторяющиеся значения здесь естественны: правило использует слагаемые с одинаковыми начальными значениями. Затем и .
В литературе встречается другая нумерация: три начальные единицы могут обозначаться , а не . Тогда один и тот же список чисел сохраняется, но номер каждого его элемента меняется. В работе Alain Faisant о последовательности Падована используется запись рекурсии со сдвигом индексов; поэтому перед сравнением ответов всегда проверяйте начальные условия.
У чисел Фибоначчи сумма берётся по двум непосредственно предшествующим членам. У Падована предыдущий член в исходной формуле не участвует. Оба правила линейные, но порождают разные последовательности и разные предельные отношения.
Как вычислить число по номеру
Для ручного счёта удобно составить таблицу и не пропускать индексы:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 7 | 9 | 12 |
Пусть требуется найти . По формуле нужны и , а не и . Из таблицы и , поэтому
Для следующего шага снова меняем оба индекса: . Такой порядок полезен и в программе: достаточно хранить три последние величины, вычислять сумму первой и второй из них и сдвигать окно на одну позицию. Для малых номеров таблица прозрачнее, а при больших последовательное вычисление избавляет от повторного пересчёта одних и тех же членов.
Начальные условия обязательны. Одна рекурсия сама по себе не определяет единственную последовательность: если заменить тройку единиц другой тройкой, дальнейшие значения тоже изменятся. Поэтому в задаче проверяют и правило, и стартовые числа.
Пластическое число и отношение соседних членов
Посмотрим на отношения . В начале они колеблются: , затем , а . По мере роста номера колебания затухают, и отношение стремится к пластическому числу .

Откуда берётся это число? Подставим пробное решение вида в рекуррентную формулу и разделим на при :
У этого уравнения один действительный корень и два комплексно-сопряжённых корня. Их модули меньше единицы: произведение всех трёх корней равно единице, следовательно квадрат модуля комплексного корня равен . Общее решение рекурсии складывается из степеней трёх корней. Для выбранных начальных условий коэффициент при положителен: иначе последовательность, которая неограниченно растёт, стремилась бы к нулю. Поэтому два остальных вклада затухают относительно главного, и .
Это объяснение сильнее одной лишь подстановки предполагаемого предела в формулу: подстановка показывает, какому уравнению предел обязан удовлетворять, но сама по себе не доказывает существование предела. Значение и связь пластического числа с последовательностью приводятся также в OEIS. В отличие от золотого сечения, возникающего у Фибоначчи, здесь определяющее уравнение кубическое.
Предельное отношение говорит о долговременном масштабе роста, а не об одинаковом процентном увеличении на каждом шаге. Ранние отношения то больше, то меньше предела; поэтому умножение текущего значения на не заменяет точную рекурсию. При достаточно большом номере главный вклад имеет вид постоянного множителя на , но начальный множитель зависит от выбранных стартовых условий.
На графике каждая точка соответствует целому номеру, а отрезки между точками только помогают проследить порядок. Никаких промежуточных членов с дробными индексами это соединение не задаёт. Пунктир показывает предельный уровень, а не значение, которое обязано быть достигнуто в какой-либо конечной точке. Различие между приближением к числу и точным равенством важно и при округлении ответа: четыре десятичных знака описывают точность записи, а не точность всех конечных отношений.
Производящая функция
Соберём все члены в формальный степенной ряд . Умножим его на . Начиная с коэффициента при , каждое выражение обращается в ноль благодаря рекурсии. Для первых трёх степеней остаются коэффициенты , и . Значит,
Например, коэффициент при в разложении этого выражения равен . Это не новое определение стартовых чисел, а компактная запись той же последовательности. Она полезна при выводе тождеств и сумм; общая техника описана в статье о методе производящих функций. Формальный ряд позволяет сравнивать коэффициенты без предположения о численном значении .
Комбинаторный смысл: дорожки из плиток
Есть модель, в которой числа Падована появляются при подсчёте. Пусть - число способов покрыть дорожку длины плитками длины 2 и 3, если порядок плиток различается. Пустую дорожку считаем покрытой одним способом: . Для отрицательных длин положим .
Последняя плитка имеет длину либо 2, либо 3. После её удаления остаётся покрытая дорожка длины или , поэтому при выполняется . Начало ряда здесь: , , , , . Значит, при нашей нумерации для всех : три начальных значения совпадают и далее действует та же рекурсия.
Например, : длину 7 дают порядки плиток , и . Разные порядки считаются разными покрытиями. Здесь применяется правило суммы в комбинаторике: два случая последней плитки не пересекаются и вместе исчерпывают все варианты.
Как организовать расчёт без таблицы
Для большого номера не обязательно хранить всю последовательность. Обозначим три соседних известных члена через , , : сначала это три единицы. Новый член равен , ведь именно эти два значения находятся на три и два шага от новой позиции. Затем заменяем тройку на и повторяем операцию. Порядок действий важен: сумму нужно вычислить до того, как старые значения будут заменены.
После первого сдвига получаем тройку , после второго - , после третьего - . Последний элемент каждой новой тройки и есть очередной член последовательности. Такой алгоритм выполняет по одному сложению на шаг и хранит только три числа. Для очень больших номеров в программе понадобится тип, поддерживающий длинные целые числа: обычный числовой тип может потерять точность, даже если сама рекурсия записана верно.
Калькулятор выше ограничен номером 25, поэтому использует точные целые значения в своём диапазоне. На последнем положении он показывает . Если нужна не только величина, но и проверка хода решения, удобнее сохранить промежуточную таблицу: по ней легко увидеть, на каком шаге были выбраны неверные индексы.
Ещё один способ проверить вычисление
Из основного правила получается полезное равенство при . В самом деле, , а . Подставляя второе равенство в исходную рекурсию и собирая первые два слагаемых, получаем нужную формулу. Например, . Она даёт независимую проверку арифметики, хотя основана на том же определении.
Это равенство также объясняет, почему при нашей тройке единиц последовательность не убывает с пятого члена: разность равна положительному . Ранние члены проверяются непосредственно по таблице. В начальной части возможны равенства соседей, но начиная с указанного места каждое следующее число строго больше предыдущего. При работе с другими начальными условиями этот вывод заново проверяют: знак разности зависит от знака соответствующего более раннего члена.
Сравнение с другими последовательностями
Рекурсия задаёт зависимость между элементами, но сами элементы могут означать разные объекты. Числа Падована неотрицательны и со временем растут; в модели плиток они считают варианты покрытий. Последовательность Туэ - Морса, напротив, состоит из нулей и единиц и строится по другому правилу. При сравнении последовательностей важно смотреть не только на первые несколько совпавших членов, но и на определяющий закон.
Например, среди первых значений Падована встречаются , знакомые по Фибоначчи. Это не означает, что дальнейшие члены совпадут: в одном случае используется сумма соседей, в другом - членов с отступами два и три. Одинаковое значение при разных индексах также не делает правила эквивалентными.
Частые ошибки
- Складывать соседние члены. Для нужны и , а не и .
- Забывать нулевой индекс. Если нумерация начинается с единицы, номер искомого элемента в той же записи чисел сдвигается.
- Считать раннее отношение равным пределу. лишь приближает ; на малых индексах отношения заметно колеблются.
- Применять модель плиток без сдвига. При принятом здесь определении , а не .
FAQ
Почему нужны три начальных значения?
Первый вычисляемый член использует и , а следующий - и . Поэтому правило требует задать стартовое окно из трёх членов, прежде чем продолжать расчёт.
Могут ли два соседних числа совпадать?
Да. Уже в начале . Равенство соседей не нарушает рекурсию, поскольку ни один из них не обязан равняться сумме непосредственно предшествующих значений.
Является ли пластическое число рациональным?
Нет. По теореме о рациональных корнях возможные целые рациональные корни многочлена - только и , и ни один не подходит. Поэтому его действительный корень иррационален.
Коротко
При последовательность задаётся правилом . Оно даёт, в частности, , а отношения соседних членов стремятся к корню . Та же рекурсия описывает покрытия плитками длины 2 и 3 после учёта сдвига индекса.
Читайте также

Числа Фибоначчи: рекуррентная формула и примеры
Числа Фибоначчи и рекуррентная формула: начальные значения, вычисление по шагам, пример со ступеньками, вычисление членов, формула Бине и связь последовательности с золотым сечением.

Числа Стирлинга первого рода: перестановки и циклы
Числа Стирлинга первого рода: что считают знаковые и беззнаковые числа, рекуррентная формула, связь с циклами перестановок, факториалом и нисходящим факториалом, разбор примеров.

Метод производящих функций: как ряд решает комбинаторику
Метод производящих функций: как закодировать последовательность в степенной ряд, вывести формулу общего члена, решить рекуррентность и сосчитать разбиения. Разбор с примерами и типовыми ошибками.

Числа трибоначчи: формула и примеры вычисления
Числа трибоначчи: три начальных значения, рекуррентная формула и расчёт по шагам. Как последовательность считает пути по ступенькам и как написать эффективный алгоритм.

Канонические преобразования и производящая функция
Канонические преобразования и производящая функция: что сохраняет каноничность, четыре типа функций F1-F4, условие на скобки Пуассона и разбор на примерах гармонического осциллятора.

Абсолютная и относительная погрешность числа
Абсолютная и относительная погрешность приближённого числа: формулы, расчёт в процентах, оценка при округлении и подробные примеры сравнения точности.