Застрял в решении рекуррентных отношений с использованием доменного преобразования (на телескопическом этапе)
Итак, я пытаюсь решить эту рекуррентную связь, используя преобразование домена:
T (1) = 1
T (n) = T ((n + 2) / 4) + 2, n> 1
Пока это то, что я пытался сделать: когда мы выполняем преобразование домена, нам нужно рассмотреть g(n) = n и, таким образом, g(n+2)= (n+2)/4.
так как у нас есть g(n) = n, мы можем подставить в g (n + 2), чтобы получить
g (n + 2) = (g (n) + 2) / 4 и упрощаем, чтобы получить g (n) = 4g (n + 2) - 2, n> 1
пока я думаю все правильно.
затем я разрываюсь между умножением на 1 / (4 ^n) и 1 / (2^n)
когда этот шаг сделан, мы можем позволить S(n) равняться либо g (n) / (4 ^n), либо g (n) / (2^n)
если мы сделаем первое, то мы можем вывести (игнорируя не-член в нашем предыдущем уравнении выше) (4g (n + 2)) / (4 ^n) и, упрощая, получаем:
г (п + 2) / (4 ^ (п-1)).
Я пытаюсь получить S(n-1), делая это, и хотя 4 возводится в n-1, данный термин явно не в этой форме.
Альтернативно, метод, к которому я больше склонен, это деление на 2^n. Если мы сделаем это, то 4 (g (n + 2)) / 2^n упрощается до:
г (п + 2) / 2 ^ (п-2).
Однако я все еще не могу получить S(n-1) или даже S(n-2), хотя последнее не кажется очень полезным.
Любое направление к этому будет оценено.