Как решить следующее отношение повторяемости

Question

Как решить следующее рекуррентное соотношение?

f(n+2) = 2*f(n+1) - f(n) + 2  where n is even
f(n+2) = 3*f(n)               where n is odd
f(1) = f(2) = 1

Для нечетных n Я могу решить повторение, и получается геометрическая серия с общим отношением 3.

Когда n является четным, я мог бы найти и решить однородную часть рекуррентного отношения, подставив f(n) = r^n. Таким образом, решение становится r = 1. Поэтому решение c1 + c2*n. Но как мне решить конкретную неотъемлемую часть? Я на правильном пути? Есть ли другие подходы к вышеуказанному решению?

Answer 1

Повторение для нечетное n очень легко решить с помощью подстановки, которую вы пытались:

Подставляя этов повторение для даже n:

---

Попытка # 1

Произведите общую замену формы:

^{Обратите внимание, что показатель степени равен n/2 вместо nна странное повторение, но это просто вопрос выбора}

Соответствие тем же типам терминов:

Но это решение не работает с граничным условием f(2) = 1:

---

Попытка # 2

Оказывается, требуется второй экспоненциальный член :

Как и раньше, одно из показательных условий должно соответствовать 3^(n/2):

Последнее уравнение имеет решения d = 0, -1;очевидно, что полезен только нетривиальный:

Окончательное решение для all n ≥ 2:

---

Альтернативный метод

Дольше, но (возможно, по крайней мере, я его нашелбыть) более интуитивным - увеличить повторяемость в m раз:

Соблюдайте шаблон:

1. Суммарный коэффициент 2 присутствует для нечетное число расширений m, но компенсируется для четное m.

2. Каждое расширение добавляет коэффициент 2 * 3^(n/2-m) для нечетное m и вычитает это для четное m.

3. Каждое расширение также добавляет коэффициент f(n-2m) для четное m,и вычитает это для нечетное m.

Объединение этих наблюдений для записи общего выражения замкнутой формы для m-горасширение:

Использование стандартной формулы для геометрических рядов на последнем шаге.

Рекурсия останавливается на f(2) = 1:

Тот же результат, что и раньше.