How many squares are there modulo $2^n$?
If we would deal with $p^n$, where p an odd prime, then we could use Hensel's Lemma, which clearly doesn't work with $2^n$.
Starting from 8, the odd residues are given by $(-1)^k3^m$, so clearly, the squares are exactly of the form $3^{2m}$ which is a quarter of them. The even residues are squares if they are divisible by 4 and the quotient is a square modulo $2^{n-2}$.
So, you get $squares(2^n)=2^{n-3} + squares(2^{n-2})$ which is easily solved.
We have $(\mathbb Z/2^n\mathbb Z)^{\times}\cong C_2\times C_{2^{n-2}}$ where $C_m$ denotes the cyclic group of order $m$, where an isomorphism is given by $(-1)^a3^b\leftarrow (a,b)$. (Proof: see Thm. 6.1, p. 25 here: http://web.mit.edu/~holden1/www/math/number-theory.pdf. Basically, show by induction that $3^{2^k}=2^{k+2}j+1$ where $j$ is odd.)
The elements in $C_2\times C_{2^{n-2}}$ that are divisible by 2 are exactly $0\times 2C_{2^{n-2}}$ which has cardinality $2^{n-3}$. We get the recurrence $\#\text{squares}(2^n)=2^{n−3}+\#\text{squares}(2^{n−2})$ as in Phira's answer.