How many Transformations?

This elaborates out my comment made in Daniel's solution, about how to use eigenvalue decomposition.

Let $A = \begin{pmatrix} 2 & 0 \\ 1 & 4 \\ \end{pmatrix}$ . We can calculate that the eigenvalues of $A$ are $\lambda_1 = 4, \lambda_2 = 2$ with corresponding eigenvectors $v_1= \begin{pmatrix} 0\\1 \end{pmatrix}$ and $v_2 = \begin{pmatrix} 2 \\ -1 \end{pmatrix}$ .

Observe that $\begin{pmatrix} 2 \\ 1 \end{pmatrix} = 2v_1 + v_2$ . Hence,

$A^N \cdot \begin{pmatrix} 2 \\ 1 \end{pmatrix} = A^N \cdot (2 v_1 + v_2) = 4^N\times 2 v_1 + 2^N\times v_2 = \begin{pmatrix} 2^{N+1} \\ 2^{2N+1} - 2^N\end{pmatrix}$

Then, continue as in Daniel's solution.

We analyze what happens when we multiply the transformation matrix $\left(\begin{array}{cc}2 & 0 \\ 1 & 4\end{array}\right)$ by a general vector $\dbinom{a}{b}$ : $\left(\begin{array}{cc}2 & 0 \\ 1 & 4\end{array}\right)\cdot \dbinom{a}{b}=\dbinom{2a}{a+4b}$

Thus, we can set up a recurrence relationship for the values of $x,y$ . Our equation is $\left(\begin{array}{cc}2 & 0 \\ 1 & 4\end{array}\right)^N\cdot \dbinom{x_0}{y_0}=\dbinom{x_N}{y_N}$ We see that $x_0=2$ and $y_0=1$ . Also, $x_n$ and $y_n$ satisfy the following recurrence relationship: $\left\{\begin{array}{l}x_n=2x_{n-1}\\ y_n=x_{n-1}+4y_{n-1}\end{array}\right.$

We can first immediately notice that since $x_0=2$ and $x_n=2x_{n-1}$ , then obviously $x_n=2^{n+1}$ .

Thus, we just need to find the general form of the recurrence $y_n=2^n+4y_{n-1}$

Note that $y_{n+1}=2^{n+1}+4y_n$

If we double the original equation $2y_n=2^{n+1}+8y_{n-1}$

we can subtract it from this the new equation we found: $y_{n+1}-2y_n=4(y_n-y_{n-1})$

Now let $z_n=y_{n+1}-2y_n$ . Thus, $z_n=4z_{n-1}$

We see that $y_0=1$ and $y_1=6$ by computation. Thus, $z_0=4$ and it is obvious our general form for $z_n$ is $z_n=4^{n+1}$

Thus, $y_{n+1}-2y_n=4^{n+1}$ . Note that $2y_n-4y_{n-1}=2\cdot 4^n$ ; we can add this to our first equation to get $y_{n+1}-4y_{n-1}=4^{n+1}+2\cdot 4^n$ . We can continue adding similar terms until we create a telescoping sum, where we conclude that $y_{n+1}=\sum_{i=0}^{n+1}2^i4^{n+1-i}=\sum_{i=0}^{n+1}2^{2n+2-i}$

But $\sum_{i=0}^{n+1}2^{2n+2-i}=\sum_{i=0}^{2n+2}2^i-\sum_{i=0}^{n}2^i=2^{2n+3}-2^{n+1}$

Thus, $y_{n+1}=2^{2n+3}-2^{n+1}$ or $y_n=2^{2n+1}-2^n$

We now have both general forms of $x_n$ and $y_n$ ; thus, we can find $x_N$ and $y_N$ : $x_N=2^{N+1}$ $y_N=2^{2N+1}-2^N$

Thus, $\begin{aligned}\log_2 (x_Ny_N)&=\log_2 (2^{3N+2}-2^{2N+1})\\ &=(2N+1)+\log_2 (2^{N+1}-1) \\ &< (2N+1)+\log_2(2^{N+1})\\ &= 3N+2\\ &\le 1000\end{aligned}$

Since $3N+2 \le 1000$ , we have $N \le \dfrac{998}{3}$ or $N \le \boxed{332}$ and we are done.

I tried to find ${ \begin{pmatrix} 2 & 0 \\ 1 & 4 \end{pmatrix} }^{ n }$ by multiplying the matrix $\begin{pmatrix} 2 & 0 \\ 1 & 4 \end{pmatrix}$ two three times with itself and found some relation like $\begin{pmatrix} { 2 }^{ n } & 0 \\ { 2 }^{ 2n-1 }-{ 2 }^{ n-1 } & { 4 }^{ n } \end{pmatrix}$ and then multiplied it to $\begin{pmatrix} 2 & \\ 1 & \end{pmatrix}$ and obtained $x={ 2 }^{ n+1 }$ and $y={ 2 }^{ 2n+1 }-{ 2 }^{ n }$ and on solving we get $n=332.$