Exams › GATE › Engineering Mathematics
Statement for Linked Answer Questions 78 and 79:
Let xₙ denote the number of binary strings of length n that contain no consecutive 0s.
Which of the following recurrences does xₙ satisfy?
- xₙ = 2xₙ₋₁
- xₙ = x_([n/2]) + 1
- xₙ = x_([n/2]) + n
- xₙ = xₙ₋₁ + xₙ₋₂
Correct answer: xₙ = xₙ₋₁ + xₙ₋₂
Solution
The recurrence relation xₙ = xₙ₋₁ + xₙ₋₂ correctly accounts for the construction of binary strings of length n without consecutive 0s. A valid string can either end with a 1 (which allows any valid string of length n-1 before it) or end with a 0 (which must be preceded by a 1, thus allowing any valid string of length n-2 before it).
Related GATE Engineering Mathematics questions
- What are the eigenvalues of the matrix [2, 1, 1; 1, 4, 1; 1, 1, 2]?
- A circle with center at (x,y) = (0.5, 0) and radius = 0.5 intersects with another circle with center at (x,y) = (1,1) and radius = 1 at two points. One of the points of intersection (x,y) is:
- Suppose λ is an eigenvalue of matrix A and x is the corresponding eigenvector. Let x also be an eigenvector of the matrix B = A − 2I, where I is the identity matrix. Then, the eigenvalue of B corresponding to the eigenvector x is equal to
- Let A = [[1, 1], [1, 3], [−2, −3]] and b = [b1, b2, b3]. For Ax = b to be solvable, which one of the following options is the correct condition on b1, b2, and b3:
- If the quadrantal bearing of a line is N 30° W, then the whole circle bearing of the line is
- The matrix [2, -4; 4, -2] has
⚔️ Practice GATE Engineering Mathematics free + battle 1v1 →