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!
Best Answer
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