If f(n) = 5f(n/2) + 3 and f(1) = 7 is a recurrence relation, where 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
With aₖ = f(2ᵏ): aₖ = 5aₖ₋₁ + 3, a₀ = 7. The solution is aₖ = 5ᵏ·7 + 3(5ᵏ − 1)/4 = 5ᵏ(31/4) − 3/4.More Discrete Structures and Optimisation 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ₙ is a solution of the recurrence relation aₙ = 8aₙ₋₁ − 16aₙ₋₂? A. aₙ = 1 B. aₙ = 2ⁿ C. aₙ = 4ⁿ D. aₙ = n…
- Arrange the following simple graphs by the number of spanning trees they have (increasing): A. K₃ (complete graph on 3 nodes) B. K₄ (comple…
- A bit string of length four is generated at random. What is the probability that it contains at least two consecutive 0s, given that the fi…
- Arrange the following sets in increasing order of their cardinality: A. A1 = {{1, 2}, {3}} B. A2 = {{1}, {2}, {3}, {4}} C. A3 = {{1, 2, 3,…
- The chairs of an auditorium are to be labelled with a letter followed by a positive two-digit integer, starting with A01. What is the maxim…