Question

A sequence x[n] is specified as:

\(\left[ {\begin{array}{*{20}{c}} {{\rm{x}}\left[ {\rm{n}} \right]}\\ {{\rm{x}}\left[ {{\rm{n}} - 1} \right]} \end{array}} \right] = {\left[ {\begin{array}{*{20}{c}} 1&1\\ 1&0 \end{array}} \right]^{\rm{n}}}\left[ {\begin{array}{*{20}{c}} 1\\ 0 \end{array}} \right],{\rm{\;for\;n}} \ge 2.\)

The initial conditions are x[0] = 1, x[1] = 1, and x[n] = 0 for n < 0. The value of x[12] is ________.

Answer 1

\(\left[ {\begin{array}{*{20}{c}} {x\left( n \right)}\\ {x\left( {n - 1} \right)} \end{array}} \right] = {\left[ {\begin{array}{*{20}{c}} 1&1\\ 1&0 \end{array}} \right]^n}\left[ {\begin{array}{*{20}{c}} 1\\ 0 \end{array}} \right],n \ge 2\)

For n = 2:

\(\left[ {\begin{array}{*{20}{c}} {x\left( 2 \right)}\\ {x\left( 1 \right)} \end{array}} \right] = {\left[ {\begin{array}{*{20}{c}} 1&1\\ 1&0 \end{array}} \right]^2}\left[ {\begin{array}{*{20}{c}} 1\\ 0 \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 2&1\\ 1&1 \end{array}} \right]\left[ {\begin{array}{*{20}{c}} 1\\ 0 \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 2\\ 1 \end{array}} \right]\)

x(2) = 2, x(1) = 1

For n = 3:

\(\left[ {\begin{array}{*{20}{c}} {x\left( 3 \right)}\\ {x\left( 2 \right)} \end{array}} \right] = {\left[ {\begin{array}{*{20}{c}} 1&1\\ 1&0 \end{array}} \right]^3}\left[ {\begin{array}{*{20}{c}} 1\\ 0 \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 3&2\\ 2&1 \end{array}} \right]\left[ {\begin{array}{*{20}{c}} 1\\ 0 \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 3\\ 2 \end{array}} \right]\)

x(3) = 3, x(2) = 2

From the above values we can write the recursive relation as

x(n) = x(n – 1) + x(n – 2)

x(2) = x(1) + x(0) = 1 + 1 = 2

x(3) = x(2) + x(1) = 2 + 1 = 3

x(4) = x(3) + x(2) = 3 + 2 = 5

x(5) = x(4) + x(3) = 5 + 3 = 8

x(6) = x(5) + x(4) = 8 + 5 = 13

x(7) = x(6) + x(5) = 13 + 8 = 21

x(8) = x(7) + x(6) = 21 + 13 = 34

x(9) = x(8) + x(7) = 34 + 21 = 55

x(10) = x(9) + x(8) = 55 + 34 = 89

x(11) = 89 + 55 = 44

x(12) = 144 + 89 = 233