GATE 2016 EC – Question 37
A sequence $x[n]$ is specified as
$$\begin{bmatrix} x[n] \\ x[n-1] \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \text{ for } n \geq 2.$$
The initial conditions are $x[0] = 1$, $x[1] = 1$, and $x[n] = 0$ for $n < 0$. The value of $x[12]$ is ________
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 230 to 240
Explanation
Powers of the matrix $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ generate Fibonacci numbers: $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix}$ with $F_1 = F_2 = 1$. So $x[n] = F_{n+1}$, which matches $x[0] = x[1] = 1$. Then $x[12] = F_{13} = 233$.