This is obviously true. We denote $n_x = x^2 + x$. Note that $n_x \equiv 0 \pmod{2} \forall x \in \mathbb{Z}^+$, thus $\frac{n_x}{2} \in \mathbb{Z}^+ \forall x \in \mathbb{Z}^+$. We now make use of the identity $n_{a+b} = n_a + n_b + 2ab$. If $n_m = a_1 + a_2 + \ldots + a_k$ for some $k \in \mathbb{Z}^+, a_i \in M$ for $i = 1, 2, \ldots , k$, then from our identity, we have \[ n_{(\frac{n_m}{2} + 1)} = n_{\frac{n_m}{2}} + n_1 + n_m = n_{\frac{n_m}{2}} + n_1 + a_1 + a_2 + \ldots + a_k \] This means that if $n_p$ can be expressed as a sum of $k$ $n_i$'s, then we can find another $n_q$ that can be expressed as a sum of $(k+2)$ $n_i$'s. Finally, we note that $n_3 = n_2 + n_2$ and that $n_2 = n_1 + n_1 + n_1$ and we are done.

I wonder if the problem really wants distinct elements? Otherwise the case $ k\geq 3$ can just be solved by the fact that $ n_{k+1} = n_k + (k+1)n_1$

prowler wrote: Let $ M = \{x^2 + x \mid x\in \mathbb N^{\star} \}$. Prove that for every integer $ k\geq 2$ there exist elements $ a_{1}, a_{2}, \ldots, a_{k},b_{k}$ from $ M$, such that $ a_{1} + a_{2} + \cdots + a_{k} = b_{k}$. Let $ x_i = \sqrt {4a_i + 1}$. Then $ x_i \in \mathbb{R}$ and $ x_i$ can be any odd natural number $ \ge 3$. Likewise let $ y = \sqrt {4b_k + 1}$. So it suffices to prove that there exists odd natural numbers $ x_1,x_2,...,x_k,y \ge 3$ such that: $ x_1^2 + x_2^2 + \cdots + x_k^2 = y^2 + (k - 1)$ Or equivalently: $ y^2 - x_k^2 = x_1^2 + x_2^2 + \cdots + x_{k - 1}^2 - (k - 1)$ Let $ y = x_k + 2$. Then $ y^2 - x_k^2 = 4x_k + 4$ So we have: $ x_k = \frac {x_1^2 + x_2^2 + \cdots + x_{k - 1}^2 - (k - 1)}{4} + 1$ It is apparent that $ x_i^2 \equiv 1 \bmod 8$ and therefore $ \frac {x_1^2 + x_2^2 + \cdots + x_{k - 1}^2 - (k - 1)}{4}$ is even and hence $ x_k$ is odd. If we just make $ x_1,x_2,...,x_{k - 1}$ "large" and define $ x_k$ as above and $ y = x_k + 2$ we find a solution where all the numbers are different.

It is obvious that $ 2 \in M$. For $ k = 2$, we have that $ (2^2 + 2) + (2^2 + 2) = (3^2 + 3)$. For each $ k \geq 3$, we have that $ 2 + 2 + .. + 2 + (k - 2)^2 + (k - 2) = (k - 1)^2 + (k - 1)$ (there are $ k - 1$ 2's)

Assuming the elements must be distinct, we can prove it by induction on $ k$. The base case is obvious as $ 12 + 30 = 42$ Now assume the problem is true for up to $ k = n$. Then, $ a_1 + a_2 + ...a_n = y^2 + y$ for some $ y$. To prove the original statement for $ k = n + 1$, take $ a_{n + 1} = (\frac {y^2 + y}{2} - 1)^2 + (\frac {y^2 + y}{2} - 1)$ and leave all the other $ a_n$'s the same. Then, $ a_1 + a_2 + ...a_n + a_{n + 1} = y^2 + y + (\frac {y^2 + y}{2} - 1)^2 + (\frac {y^2 + y}{2} - 1) = \frac {(y^2 + y)^2}{4} + \frac {y^2 + y}{2}$ which is of the desired form.