Recurrence relation for $A002249_{(2^n-1)}$
I'm interested about the sequence A002249 in the OEIS and I have a question about this sequence :
$$a_n = a_{n-1} - 2a_{n-2};\, a_0 = 2, a_1 = 1.$$
Is it possible to find a reccurence relation for $a_{2^n-1}$ with that form $a_{2^n-1} = ba_{n-1}^p - ca_{n-2}^q - ... - da_{n-m}^r$ ?
Here is what I observed :
You can write the sequence with that tips (start at $n=2, a_{2^n-1} = -5$):
For example :
- $a_3 = -5$
- $a_7 = (-5)\cdot1-2^3 = -13$
- $a_{15} = ((-5)\cdot1-2^3)\cdot(1^2-2^5)-2^7 = 275$
- $a_{31} = (((-5)\cdot1-2^3)\cdot(1^2-2^5)-2^7)\cdot((1^2-2^5)^2-2^9)-2^{15} = 90707$
- $a_{63} = ((((-5)\cdot1-2^3)\cdot(1^2-2^5)-2^7)\cdot((1^2-2^5)^2-2^9)-2^{15})\cdot(((1^2-2^5)^2-2^9)^2-2^{17})-2^{31} = 4249990355$ etc.
By generalization you can write : $a_{2^n-1} = ((((((((-5)\cdot1-2^3)\cdot(1^2-2^5)-2^7)\cdot((1^2-2^5)^2-2^9)-2^{15})\cdot(((1^2-2^5)^2-2^9)^2-2^{17})-2^{31})\cdot((((1^2-2^5)^2-2^9)^2-2^{17})^2-2^{33})-2^{63})-...-2^{2^{n-2}+1})^2-2^{2^{n-1}+1})-2^{2^{n}-1}$
But I have no idea how to have a sequence from this.
Can you help me please ?
You can get a recurrence using two sequences, where one is the sequence you want. Don't know if you can do better.
Show that $$a_{2k}=a_k^2-2^{k+1}.$$
Then let $b_n=a_{2^n -1}, c_n=a_{2^n}.$
Then when $k=2^n$ in $(1),$ we get $$c_{n+1}=c_n^2-2^{2^{ n}+1}.$$
And when $k=2^n-1$ in $(1),$ we get $$b_n^2-2^{2^n}=a_{2^{n+1}-2}=\frac{b_{n+1}-c_{n+1}}2$$
Re-arranging, we get: $$b_{n+1}=2b_{n}^2-2^{2^n+1}+c_{n+1}=2b_n^2+c_n^2-2^{2^n+2}$$
So you can compute $(b_{n+1},c_{n+1})$ in terms of $(b_n,c_n).$