błagam o pomoc elza: Znajdź postać jawną dla ciągu zdefiniowanego rekurencyjnie a(n)=3a([ⁿ₂]) a(1)=2 Wydedukuj z postaci jawnej asymptotykę a(n)=0

Basia: a₂ = 3a₁ = 6 = 2*3 a₃ = 3a₁ = 6 = 2*3 a₄ = 3a₁ = 18 = 2*3² a₅ = 3a₂ = 18 = 2*3² a₆ = 3*a₃ = 54 = 2*3³ a₇ = 3*a₃ = 54 = 2*3³ a₈ = 3a₄ = 162 = 2*3⁴ a₉ = 3a₄ = 162 = 2*3⁴ a_n = 2*3^[n/2] dla n≥2 asymptotyka a(n)=0 ? przecież to jest ciąg rozbieżny do +∞

Trivial: a(n) = 3a([n/2]) = 3²a([n/2²]) = 3³a([n/2³]) = ... = 3^ka([n/2^k]) Chcemy aby [n/2^k] = 1. Taki warunek spełnia k = [lg(n)], lg = log₂, zatem a(n) = 3^[lg(n)]a(1) = 2*3^[lg(n)] ← postać jawna wzoru na a_n. Oszacowanie asymptotyczne: Dokonajmy podstawienia [lg(n)] = lg(n) − ε, ε∊[0,1).

	2
a(n) = 2*3lg(n)−ε =		3lg(n)
	3ε

3^lg(n) = 3^{log₃n/log₃2} = n^1/log₃2 = n^log₂3 = n^lg3.

	2
a(n) =		nlg3
	3ε

Bez trudu zauważamy, że skoro 0 ≤ ε < 1, to

	2
		nlg3 < a(n) ≤ 2nlg3
	3

A zatem a(n) = Θ(n^lg3) = O(n^1.585)