Kanada 2011

Let $U_k=(1+kd{)}^2$. We calculate $U_{k+3}-U_{k+2}-U_{k+1}+U_k$. This turns out to be $4d^2$, a constant. Changing signs, we obtain the sum $-4d^2$. Thus if we have found an expression for a certain number $S_0$ as a sum of the desired type, we can obtain an expression of the desired type for $S_0+(4d^2)q$, for any integer $q$.

It remains to show that for any $S$, there exists an integer $S^{\prime }$ such that $S^{\prime }\equiv S(\mathrm{mod}4d^2)$ and $S^{\prime }$ can be expressed in the desired form. Look at the sum $$(1+d{)}^2+(1+2d{)}^2+\cdots +(1+Nd{)}^2,$$ where $N$ is "large." We can at will choose $N$ so that the sum is odd, or so that the sum is even. By changing the sign in front of $(1+kd{)}^2$ to a minus sign, we decrease the sum by $2(1+kd{)}^2$. In particular, if $k\equiv 0(\mathrm{mod}2d)$, we decrease the sum by $2$ (modulo $4d^2$). So If $N$ is large enough, there are many $k<N$ such that $k$ is a multiple of $2d$. By switching the sign in front of $r$ of these, we change ("downward") the congruence class modulo $4d^2$ by $2r$. By choosing $N$ so that the original sum is odd, and choosing suitable $r<2d^2$, we can obtain numbers congruent to all odd numbers modulo $4d^2$. By choosing $N$ so that the original sum is even, we can obtain numbers congruent to all even numbers modulo $4d^2$. This completes the proof. $\square$