Induction Squares Proof Prove that for every positive integer $n$ there exist positive integers $$a_{11}, a_{21}, a_{22}, a_{31}, a_{32}, a_{33}, \dots ,a_{n1}, a_{n2},\dots,a_{nn}$$
such that
$$
a_{11}^2 = a_{21}^2 + a_{22}^2 = a_{31}^2 + a_{32}^2 + a_{33}^2 = a_{n1}^2 + a_{n2}^2 + \cdots + a_{nn}^2.
$$
We're doing a chapter on proofs by induction so I'm pretty sure that would be the way to go. My general thought is to somehow prove that a square exists that can be the sum of any number of squares but I'm not too sure. Thank you for the help!
 A: We prove by induction.
The statement holds true for $n = 2$. Suppose it holds true for $n$, there exists the $\{a_{ij}\}_{1\le j \le i\le n}$ such that
$$
\begin{align}
a_{11}^2 & = a_{21}^2 + a_{22}^2\\
& = a_{31}^2 + a_{32}^2 + a_{33}^2\\
& = \cdots\\
& =a_{n1}^2 + a_{n2}^2 + \cdots + a_{nn}^2 \\
\end{align}
$$
For $n+1$, take $b_{22} = \color{red}{2}a_{11}$, then choose $b_{21} = a_{11}^2-1$ and $b_{11} = a_{11}^2+1$ then
$$b_{11}^2 = b_{21}^2 +b_{22}^2$$
Remark: How I find $(b_{22},b_{21},b_{11})$? The idea here is to apply the Euclid's formula, there exists $(m,n) = (a_{11},1)$ such that
$$
\begin{cases}
b_{22} = \color{red}{2} \times a_{11} \times 1 = 2mn\\
b_{21} = m^2 -n^2\\
b_{11} = m^2+n^2
\end{cases}
$$
Then, take
$$
\begin{cases}
b_{k1} = b_{21} = a_{11}^2 +1  \quad  \text{for } 2\le k \le n\\
b_{ij} = \color{red}{2}a_{(i-1),(j-1)}  \quad  \text{for } 2 \le j \le i \le n+1\\
\end{cases}
$$
So,  there exists $\{b_{ij}\}_{1\le j \le i\le n+1}$ such that
$$
\begin{align}
b_{11}^2 & = b_{21}^2 + a_{11}^2= b_{21}^2 + b_{22}^2\\
& = b_{31}^2 + a_{11}^2 = b_{31}^2 + b_{32}^2 + b_{33}^2\\
& = \cdots\\
& = b_{(n+1),1}^2 + a_{11}^2 =b_{(n+1),1}^2 + b_{(n+2),2}^2 + \cdots + b_{(n+1),(n+1)}^2
\end{align}
$$
Q.E.D
A: We proof by induction. You have already found the initial case.
$$5^2 = 3^2 + 4^2$$
We now use the formula
$$\left(\frac{x^2+1}2\right)^2=x^2+\left(\frac{x^2-1}2\right)^2$$ to find a sequence
$$z^2_n=x^2_n+y^2_n$$
such that $x_n=z_{n-1}$.
$$\begin{array}{r,r,r}
5^2&=&4^2&+&3^2\\
13^2&=&12^2&+&5^2\\
85^2&=&84^2&+&13^2\\
3613^2&=&3612^2&+&85^2\\
6 526 885^2&=&6 526 884^2&+&3613^2\\
&\cdots&&&&&
\end{array}$$
From this we get
$$\begin{eqnarray}
6 526 885^2\\
=6 526 884^2&+&3613^2\\
=6 526 884^2&+&3612^2+85^2\\
=6 526 884^2&+&3612^2+84^2+13^2\\
=6 526 884^2&+&3612^2+84^2+12^2+5^2\\
=6 526 884^2&+&3612^2+84^2+12^2+4^2+3^2
\end{eqnarray}
$$
So we have found a number that can be represented as the  sum of 1, 2, 3, 4, 5 or 6 squares. I think it is clear to continue this process and how to proof it by induction.
