The solution to the recurrence equation T(2ᵏ) = 3T(2ᵏ⁻¹) + 1, T(1) = 1, is:
2002
The solution to the recurrence equation T(2ᵏ) = 3T(2ᵏ⁻¹) + 1, T(1) = 1, is:
- A.
2ᵏ
- B.
(3ᵏ⁺¹ - 1)/2
- C.
3 log₂ k
- D.
2 log₃ k
Attempted by 9 students.
Show answer & explanation
Correct answer: B
The correct answer is Option B. Let Sₖ = T(2ᵏ). Since T(1) = T(2⁰) = 1, we have S₀ = 1. The recurrence becomes Sₖ = 3Sₖ₋₁ + 1. Expanding it gives Sₖ = 3ᵏS₀ + (1 + 3 + 3² + ... + 3ᵏ⁻¹). Substituting S₀ = 1, Sₖ = 3ᵏ + (3ᵏ - 1)/2 = (2·3ᵏ + 3ᵏ - 1)/2 = (3ᵏ⁺¹ - 1)/2. Therefore, T(2ᵏ) = (3ᵏ⁺¹ - 1)/2.