How to find all possible solutions to $a^2 + b^2 = 2^k$? I'm working on the following problem, this is for an introductory discrete mathematics class.
Find all possible solutions to the equation $a^2 + b^2 = 2^k, k\geq1$ and $a$ and $b$ positive integers.
I've observed that the following are answers:
$2^1 = 1^2 + 1^2$
$2^3 = 2^2 + 2^2$
$2^5 = 4^2 + 4^2$ or $2^5 = 2^4 + 2^4$
From that, there seems to be a pattern such as $2^{k+1}=2^k + 2^k$ for some even $k \geq 0$
I've also been able to observe that $k$ has to be odd. I've tried the following:
$k = 2l + 1$ for some $l$
$2^{2l+1} = a^2 + b^2$
$2^l.2 = a^2 + b^2$ Now, if I set $a=b$
$2.2^l = 2a^2$ <=> $2^l = a^2$
But I don't know how to prove that $a$ has to be equal to $b$
Also, in the case where $k$ is even:
$k=2l$ for some $l$
$2^{2l}$ = $a^2 + b^2$ Again, setting $a=b$
$2^{2l+1} = a^2$
$2^{(2l-1)/2} = a^2$ where $(2l-1)/2$ is not an integer.
But again, I don't know how to go about it when $a \neq b$.
Am I on the right path? Any tips or suggestions on how to go forward?

Your statement that $2^{k+1} = 2^k + 2^k$ is proven correct by the observation on the right-hand side that for any integer $c$, $c + c = 2c$. My first thought is that $a,b$ must have the same parity for this to ever work.
If both are even, let $a = 2A$ and $b = 2B$, so that $a^2 + b^2 = 4A^2 + 4B^2 = 4(A^2 + B^2)$. This factorization should help you.
If both are odd, let $a = 2k + 1$ and let $b = 2l + 1$, so that 
$$a^2 + b^2 = (2k+1)^2 + (2l+1)^2 = ...$$
Keep going and you should get something interesting with this. Hope that helps!
