# Show that every power of $2$ is sum of two squares.

I have to show, that every number of the form $2^n$ ($n \in \mathbb{N}$) is a sum of two squares. I don't have any idea how to start here.

Any help is appreciated.

-
It's false that every number $n$ is a sum of two squares: $3$ is not a sum of two squares (and in general, no number of the form $4n+3$ is a sum of two squares; and there are others, e.g., $21$ is not a sum of two squares). Fermat's Christmas Theorem characterizes the numbers that are sums of two squares. – Arturo Magidin Jan 19 '12 at 17:53
Oh yes ofc, you are right, I changed it above – ulead86 Jan 19 '12 at 17:56
And along the way, obliterated the grammar and tag changes that had already been made to your post... – Arturo Magidin Jan 19 '12 at 17:57
@Daniel: A negative, but I hope helpful, comment on "I don't know how to start here." Start with $n=1$, then do $n=2$, then do $n=3$, and so on. Soon everything will be clear. Here goes: $2^1=2=1^2+1^2$; $2^2=4=2^2+0^2$; $2^3=8=2^2+2^2$; $2^4=4^2+0^2$; $2^5=4^2+4^2$; $2^6=8^2+0^2$. The pattern is obvious, and now that we know what it is, writing down a formal proof is not hard. Note that the pattern is different for $n$ odd than for $n$ even. – André Nicolas Jan 19 '12 at 18:24
@André: Yes you are right, I just didn't saw the pattern, nevertheless it's obvious :/ – ulead86 Jan 19 '12 at 19:02

The statement that every natural number $n$ is a sum of two squares is false. For example, $3$ is not a sum of any two squares.

Hint: Note that $2^n=2^{n-1}+2^{n-1}$ and $2^n=2^n+0$. Which statement should you use for which $n$?

-
$2^n=2^{n-1}+2^{n-1}$ for odd n's and the other statement for even n's? – ulead86 Jan 19 '12 at 18:05
@Daniel: Exactly :) – Zev Chonoles Jan 19 '12 at 18:06
Ok I got it, thanks for the hint :-) – ulead86 Jan 19 '12 at 18:07

Hint:

1. Show that if $a$ and $b$ are each a sum of two squares, then so is $ab$.

2. Then show that $2$ is a sum of two squares.

3. Then use induction.

-

HINT $\rm\quad 2\ (a^2 + b^2)\ =\ (a + b)^2 + (a - b)^2\$ yields the inductive step.

REMARK $\$ Writing $\ 2\ = 1^2 + 1^2\$ shows that the above is nothing but a special case of the well-known Brahmagupta–Fibonacci identity for composing sums of squares. This special doubling case was known much earlier than the general case. It plays a key role in my speculative reconstruction of $\rm\ FLT_4\equiv$ Fibonacci's Lost Theorem, the area of an integral pythagorean triangle $\rm\ne n^2\:.$

-