If f(n) = 5f(n/2) + 3 and f(1) = 7, where n = 2ᴷ and K is a positive integer, then f(2ᴷ) =
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. 5ᴷ(31/4) − 3/4
Explanation
Unrolling: f(2ᴷ) = 5ᴷ·f(1) + 3(1 + 5 + … + 5ᴷ⁻¹) = 7·5ᴷ + 3(5ᴷ − 1)/4 = 5ᴷ(7 + 3/4) − 3/4 = 5ᴷ(31/4) − 3/4.
More Discrete Structures and Optimization questions
- Which of the following are true if the universe of discourse consists of all integers? A. ∀n∃m (n² < m) B. ∃n∀m (n < m²) C. ∃n∃m (n² + m² =…
- Which of the following sequences aₙ are solutions of the recurrence aₙ = 8aₙ₋₁ − 16aₙ₋₂? A. aₙ = 1 B. aₙ = 2ⁿ C. aₙ = 4ⁿ D. aₙ = n·4ⁿ E. aₙ…
- Arrange the following simple graphs based on a number of spanning trees they have : A. K [Complete Graph with 3 nodes] 3 B.K [Complete Grap…
- Match List - I with List - II.
- Arrange the following sets in increasing order of cardinality: A. A₁ = {{1, 2}, {3}} B. A₂ = {{1}, {2}, {3}, {4}} C. A₃ = {{1, 2, 3, 4, 5,…
- The chairs of an auditorium are to be labelled with a letter followed by a positive two digits integer where labelling is starting with A01…