Функции T1(n) и T2(n) заданы рекуррентными формулами, известно что Ti(1) = Ti(2) = Ti(3) = 1, i = 1,2. 1) Докажите, что для функции T2(n) = T2(n-1) + 4T2(n-3) (при n > 3) справедлива оценка log T2(n) = θ(n). 2) Найдите (точную) асимтотику роста функции T2(n). задан 25 Фев '20 12:40 Buba |
T1(n) зачем? Сама задача совершенно стандартная для рекуррентных соотношений: $%T2(n) \sim a^n$, где a - максимальный по модулю корень соответствующего характеристического уравнения%