По-моему, та же идея, что и в
этой задаче.
Не вижу как можно использовать эту идею здесь. Всё-таки

экспоненциально зависят от

. Есть аналогичная задача, где вместо последовательности

фигурирует геометрическая прогрессия, но и она решается не слишком просто. (А может быть, я не вижу каких-то простых подходов?)
-- Сб апр 16, 2011 18:05:06 --Кажется, такого многочлена нет, кроме тривиального

, а жаль.
Пусть

, причем

. Тогда свободный член многочлена равен 1 и поскольку все коэффициенты целые, то

, где

. Нетрудно найти, что

, откуда поскольку

будет

. Докажем по индукции, что

. Для

- верно.

, а поскольку

и

, то

.
Таким образом

, откуда вывод, что

.
Можно было бы числа Фибоначчи заменить на более быстрорастущую рекуррентную последовательность 2-го порядка

В этом случае мое доказательство не проходит.
Да, похоже, это оно и есть, спасибо. Но для произвольной рекурренции 2-го порядка нужно что-то более сложное придумывать.