Ищите рекуррентное решение

в виде линейной функции от

. Оно даже довольно несложное.
У меня все получилось - я его нашел - оно точно есть. Причем оно одно.
Условие простоты в совокупности большой роли не играет: решения априори не могут иметь общий НОД, отличный от степени

, значит достаточно лишь доказать, что хотя бы одно из

не делится на

. Это несложно: надо только подобрать знак.
Ну и базис докажите.