  The purpose of this paper consists to study the sums of the type $P(n) + P(n
- d) + P(n - 2 d) + \dots$, where $P$ is a real polynomial, $d$ is a positive
integer and the sum stops at the value of $P$ at the smallest natural number of
the form $(n - k d)$ ($k \in \mathbb{N}$). Precisely, for a given $d$, we
characterize the $\mathbb{R}$-vector space ${\mathscr{E}}_d$ constituting of
the real polynomials $P$ for which the above sum is polynomial in $n$. The case
$d = 2$ is studied in more details. In the last part of the paper, we approach
the problem through formal power series; this inspires us to generalize the
spaces $\mathscr{E}_d$ and the underlying results. Also, it should be pointed
out that the paper is motivated by the curious formula: $n^2 + (n - 2)^2 + (n -
4)^2 + \dots = \frac{n (n + 1) (n + 2)}{6}$, due to Ibn al-Banna al-Marrakushi
(around 1290).
