Задача несложно решается с помощью линейных рекуррентных последовательностей. Рассмотрим многочлен

- он является аннулирующим многочленом для

, то есть

.
Доказать это можно и непосредственно. А можно заметить, что если P(x) аннулирует последовательность в указанном смысле, то и любое P(x)Q(x) тоже её аннулирует. Также, если две последовательности аннулируются многочленом, то и их сумма - тоже. Тогда

аннулирует

и

, а

аннулирует

, а из этого -

аннулирует

.
Заменим

. Непосредственно вычисляется, что

. Из соотношения

индукцией для целых неотрицательных k получаем, что

, где

.
Для

решается аналогично.