We are effectively looking for $n$ such that there are exactly $k$ pairs $(x,y) \in \mathbb{N}^2$ with: $$y^2=x^2+n \Leftrightarrow (y-x)(y+x)=n$$Setting $n=2^{2(k+1)}$ we must have: $$x+y=2^{l} \quad \quad y-x=2^{2k+2-l}$$. Giving: $$x=\frac{2^l-2^{2k+2-l}}{2} \quad \quad y=\frac{2^l+2^{2k+2-l}}{2}$$As $x,y$ are positive integers we must have $l>2k+2-l \Leftrightarrow l \geq k+2$. We must also have $2k+2-l>0 \Rightarrow l \leq 2k+1$ so there are: $$(2k+1)-(k+2)+1=k$$Pairs $(x,y)$ satisfying the condition so we're done.

@mruczek you instead of $A = \{ 1^2, 2^2, 3^3, ...\}$ meant $A = \{ 1^2, 2^2, 3^2, ...\}$ I think

Here is an other solution I found: For a positive integer $n$,let $d(n)$ be the number of positive divisors of $n$ and $f(n)$ be the number of pairs $(a,b)$ such that $n=a^2-b^2$.Problem asks to prove that $f(n)$ is surjective.We prove the following claim: Claim: If $n$ is an odd,non-square positive integer,then $d(n)=2f(n)$. Proof: If for two positive integers $a,b,n=a^2-b^2$ then $n=(a-b)(a+b)$,so there is a divisor $d$ of $n$ such that $a-b=d,a+b=\frac{n}{d}$.Now,its enough to prove that every pair $(d,\frac{n}{d})$ gives a unique and distinct pair of $(a,b)$.Of course,since $n$ is odd,$d+\frac{n}{d}$ is even and such $a,b$ exist and $a=\frac{d^2+n}{2d}$.Assume that there is a positive divisor $t$ of $n$ with $t>d$ such that $\frac{d^2+n}{2d}=\frac{t^2 +n}{2t}$ so: $$t d^2 +tn=d t^2 +dn \implies (t-d)n=(t-d)dt \implies n=dt \implies t=\frac{n}{d}$$. So each pair $(d,\frac{n}{d})$ gives a distinct pair $(a,b)$ with $n=a^2-b^2$ and obviously,these are the only solutions,so $d(n)=2f(n)$.Since the function $d(n)$ is surjective on even numbers(even with odd non-square entries,this follows immediately from the formula of $d(n)$) so $f(n)$ is also surjective and we are done.

WolfusA wrote: @mruczek you instead of $A = \{ 1^2, 2^2, 3^3, ...\}$ meant $A = \{ 1^2, 2^2, 3^2, ...\}$ I think Moderators, Please correct the error in the question. Thank you.