Recursive substitution

1) Rewrite the recurrence as: $(a_{n+2}-2^{n+1} a_{n+1})-2^{-n}(a_{n+1}-2^{n} a_{n})=0$ 2) let $b_n=a_{n+1}-2^{n} a_{n}$ , It follows that $b_1=1$ and $b_{n+1}-2^{-n} b_{n}=0$ It's easy to conclude that $b_n=2^{-\frac{n(n-1)}{2}}$ 3) We have $a_{n+1}-2^{n} a_{n}=2^{-\frac{n(n-1)}{2}}$ till now, another substitution will lead us to solution, let $a_n= c_n 2^{\frac{n(n-1)}{2}}$ , we get $c_1=1$ and $c_{n+1}-c_{n}=2^{-n^2}$ , It is clear that $c_n=\sum_{k=0}^{n-1} 2^{-k^2}$ and finally $a_n=2^{\frac{n(n-1)}{2}} \sum_{k=0}^{n-1} 2^{-k^2}$ 4) What about limit? $\lim_{n \to \infty} 2^{\frac{n(1-n)}{2}} a_n=\sum_{n=0}^{\infty} 2^{-n^2} =\frac{1}{2} \left(1+\vartheta_3 \left(0, \frac{1}{2}\right) \right)$ Regarding this formula: $\vartheta_{3} (z, q)= 1+2 \sum_{k=1}^{\infty} q^{k^2} \cos (2kz) \ ; |z|<1$