Let $d$ be a positive integer. Show that for every integer $S$, there exist a positive integer $n$ and a sequence $a_1, ..., a_n \in \{-1, 1\}$ such that $S = a_1(1 + d)^2 + a_2(1 + 2d)^2 + ... + a_n(1 + nd)^2$.
Source: 2016 Saudi Arabia BMO TST , level 4+, II p3
Tags: number theory
Let $d$ be a positive integer. Show that for every integer $S$, there exist a positive integer $n$ and a sequence $a_1, ..., a_n \in \{-1, 1\}$ such that $S = a_1(1 + d)^2 + a_2(1 + 2d)^2 + ... + a_n(1 + nd)^2$.