recursive formula for representation numbers

Question

We define the representation number $r(n,k)$ of $n$ by $k$ squares as the cardinality of the set $\{v\in\mathbb Z^k:n=v_1^2+...+v_k^2\}$.

Prove that if $i+j=k$ then $r(n,k)=\sum_{l+m=n}r(l,i)r(m,j)$.

Answer 1

Let $\mathcal R(n, k) = \{v\in\mathbb Z^k:n=v_1^2+...+v_k^2\}$. You need to show a bijection

$$ f: \mathcal R(n, k) \longleftrightarrow \biguplus_{l + m = n} \mathcal R(l, i) \times \mathcal R(m, j). $$

On the left we have vectors $v$ of length $k$, whose sum of squares equals $n$. On the right, we want a vector of length $i$ and a vector of length $j$ whose sum of squares equals $l$ and $m$ respectively.

Given a vector of length $k$, an obvious way to construct a two vectors whose lengths sum to $k$ is to split the vector in two. That is, if $v = (v_1,\dots,v_i,v_{i+1},\dots,v_k)$ then $f(v) = (u_1, u_2)$ where $u_1 = (v_1,\dots,v_i)$ and $u_2 = (v_{i + 1},\dots,v_k)$.

By construction, $u_1$ has length $i$ and $u_2$ has length $k - i = j$. If

$$ l = v_1^2 + \dots v_i^2 \text{ and } m = v_{i + 1}^2 + \dots + v_k^2, $$

then

$$ l + m = v_1^2 + \dots v_i^2 + v_{i + 1}^2 + \dots + v_k^2 = n. $$

Hence, $f(v) \in \mathcal R(l, i) \times \mathcal R(m, j)$ and $l + m = n$.

To go backwards, we take $u_1 = (v_1,\dots,v_i)$ and $u_2 = (v_{i + 1},\dots,v_k)$ and stitch them together to obtain $f^{-1}(u_1,u_2) = (v_1,\dots,v_i,v_{i+1},\dots,v_k)$.