Given M=(1110)M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}M=(1110), the sequence defined by (an+1an)=Mn(a1a0)\begin{pmatrix} a_{n+1} \\ a_n \end{pmatrix} = M^n \begin{pmatrix} a_1 \\ a_0 \end{pmatrix}(an+1an)=Mn(a1a0) follows which recurrence?
an+1=an+an−1a_{n+1} = a_n + a_{n-1}an+1=an+an−1
an+1=an−an−1a_{n+1} = a_n - a_{n-1}an+1=an−an−1
an+1=2an+an−1a_{n+1} = 2a_n + a_{n-1}an+1=2an+an−1
an+1=an+2an−1a_{n+1} = a_n + 2a_{n-1}an+1=an+2an−1