If $a_n = a_{n-1}-2a_{n-2}$ where $a_0 = 2$ and $a_1 = 1$, what is the recurrence relation for $a_{2^n}$? I'm interested about the sequence A002249 in the OEIS and I have a question about this sequence :
Is it possible to find a reccurence relation for $a_{2^n}$ with only $a_{2^n} = ba_{n-1}^p - ca_{n-2}^q - ... - da_{n-m}^r$ ?
Here is what I observed :
I found than you can write $a_{2^n} = a_{n-1}^2 - 2^{2^{(n-1)}+1}$ and you can write $2^{2^{(n+1)}+1} = \frac{b_n^2}{2}$ with $b_{0} = 4$ for $n > 2$ but I don't know how to get a formula with only $a_{n}$.
Can anyone help me please ?
EDIT : you can write the sequence as $4^{2^n} \cdot ((\frac{1}{8} - \frac{1}{8} (3 i \sqrt7))^{(2^n)} + (\frac{1}{8} + \frac{1}{8} (3 i \sqrt7))^{(2^n)})$
Not sure if it helps.
 A: 
 dl;dr: The proposed relation cannot exist.

Some useful pointers and additional information:
The sequence is known as Lucas Sequence of the 2nd kind
$$a_n = V_n = V_n(P,Q)$$
with parameters $P=1$, $Q=2$. It is filed as OEIS A002249. $V_n$ satisfies many (recurrence) relations and cross-relations to other Lucas sequences.  One of them is
$$V_{2n} = V_n^2-2Q^n = V_n^2 - 2^{n+1}$$
which
you can use to compute $V_{2^n}$ in $n$ steps starting at $V_1=1$, which might be useful. Let $a$ and $b$ denote the two distinct eigenvalues of the associated linear recurrence, i.e.
$$a,b = \frac{1\pm\sqrt{-7}}2$$
Notice that $ab=Q=2$, $a+b=P=1$ and $|a|=|b|=\sqrt2$. Then we have
$$V_n = a^n+b^n = a^n(1+b^n/a^n) = a^n(1+\varepsilon^n)$$
with $\varepsilon=(\sqrt{-7}-3)/4$ and $|\varepsilon|=|a/b| = 1$.
Hence $V_n$ grows like $|a|^n$, see for example the logarithmic scatter plots on OEIS.
Now suppose that a recurrenc relation as proposed exists, i.e. there are $m$ constants $\lambda_k$ and $e_k$ such that
$$a_{2^n} = \sum_{k=1}^m \lambda_k a_{n-k}^{e_k}\tag1$$
Then the right-hand side grows like $\mathit{const}\cdot|a|^{e(n-k)}$ where $e=\max\{e_k\}$, but the left-hand side grows like $|a|^{2^n}$.  As $|a|>1$, these two growth rates cannot be reconciled, and thus a relation like $(1)$ cannot exist.
