Can every positive integer eventually be expressed in this form?

Question

$$a=\sum_{k=0}^c(k+2)^{s_k}$$ Can every positive integer eventually be expressed in this form where $s_k\ge1$ and $c\ge0$?

My Take:
First, I'll figure out the conditions for an even/odd number
Since $k^n$ is odd when odd and even when even, $(2k+1)^n\equiv1$ mod $2$, $(2k)^n\equiv0$ mod $2$.
From this, you find that for $a$ to be even, $c=4n-1,4n$. Also, for $a$ to be odd, $c=4n+1,4n+2$.

I couldn't find anything other than this, but there is a high chance it is possible to find a proof for this statement.

Notes:
$1.$ I have found 8 numbers that cannot be expressed in this form $(1,3,6,10,12,18,24,30)$, and most are multiples of 6.
$2.$ I have checked up to $400,000$ for any counterexample.

Answer 1

Using almost exclusively just the first and second power terms, all positive integers (apart from the 8 exceptions you found) can be expressed in your specified form. First, with $s_k = 1$ for all $0 \le k \le c$, have

$$a_1 = \sum_{k=0}^{c}(k + 2) = \frac{(c + 2)(c + 3)}{2} - 1$$

For all $0 \le k \le c$, define

$$d_k = (k + 2)^2 - (k + 2) = k^2 + 3k + 2$$

i.e., the increase $a_1$ will get when $s_k$ increases to $2$. The initial set of $d_k$ values are

$$2, 6, 12, 20, 30, 42, 56, 72, \ldots$$

Using a sum of $1$ or more (at most once each) of these, there's no way to get an overall increase of $4$, $10$ or $16$, even with also using larger $s_k$ values. Otherwise, we have the following initial set of results:

$$2 = d_0, 6 = d_1, 8 = d_1 + d_0, 12 = d_2, 14 = d_2 + d_0, 18 = d_2 + d_1$$

Note $20 = d_2 + d_1 + d_0 = d_3$, so it can be obtained in more than one way. Next, using $20 = d_3$, we can get the values up to just before $30 = d_4$ by adding the results above, apart from $24$. However, that can be obtained instead by using that $3^3 - 3 = 24$. Next, using $30 = d_4$ and the cumulative results, we can obtain all of the even values up to just before $42 = d_5$ except for several exceptions, but they can be achieved by other combinations starting from $d_3$ and using the previous results. In particular, $34 = 20 + 14 = d_3 + (d_2 + d_0)$ and $40 = 20 + 20 = d_3 + (d_2 + d_1 + d_0)$. Also, these larger values can be obtained in multiple ways, e.g., $42 = 30 + 12 = d_4 + d_2$, $44 = 30 + 12 + 2 = d_4 + d_2 + d_0$, etc.

In general, using each next $d_k$ value, all of the even values up to just before $d_{k+1}$ can be obtained by adding the previous smaller results to either $d_k$ or $d_{k-1}$. Thus, apart from the exceptions of $4$, $10$ and $16$ mentioned earlier, all of the values with the same parity and larger than $a_1$ until well past $a_1 + d_c$ can be obtained.

Thus, here's an outline of how to use induction to prove my original statement, in particular by starting at $n = 1$, then going from $c = 4n$ to $c = 4(n + 1)$ for even $a$, and from $c = 4n + 1$ to $c = 4(n + 1) + 1$ for odd $a$. First, however, confirm that all $a$ values, apart from the $8$ exceptions you noted, can be obtained up to $45$. This is from $a_1 = 27$ (with $n = 1$ for odd values), so $c = 5$ and $a_1 = \frac{7\times 8}{2} - 1 = 27$, plus the first even integer addend always obtainable, i.e., $18$. Next, for even $a$ values, use the method I outlined above to show the even values from $a = a_1 + 18$ up to the next increase of $a_1$ value for $n + 1$ (i.e., $(4n + 1) + (4n + 2) + (4n + 3) + (4n + 4) = 16n + 10$, so the total is then $a = a_1 + 16n + 28$) can be obtained. Then do a similar thing for the odd $a$ values. Altogether, this proves that all larger $a$ values can be obtained.

Answer 2

Based on John Omielan's outline, I will prove below that every integer $a\geq 122$ has a representation with exponents $s_k\in\{1,2\}$.

Let us use the fact that every integer exceeding $33$ is a sum of distinct triangular numbers. Given this fact, we consider $a\geq 68$, and we define $c$ to be the largest nonnegative integer such that $$f(c):=\sum_{k=0}^c(k+2)$$ satisfies $$f(c)\equiv a\pmod{2}\qquad\text{and}\qquad f(c)\leq a-68.$$ Then $$f(c+2)=f(c)+(2c+7)>a-68,$$ whence $a-f(c)$ is an even number from $\{68,\dotsc,2c+74\}$. By the quoted fact, there are distinct nonnegative integers $k_1,\dotsc,k_m$ such that $$a-f(c)=\sum_{\ell=1}^m (k_\ell+1)(k_\ell+2).$$ We can ensure that no $k_\ell$ exceeds $c$ by imposing the condition $$(c+2)(c+3)>2c+74,$$ which is certainly satisfied for integers $c>6$. Since we have already agreed on $f(c+2)>a-68$, it suffices to assume that $a-68\geq f(8)=54$, that is, $a\geq 122$.

To sum up, every integer $a\geq 122$ can be written as $$a=f(c)+\sum_{\ell=1}^m (k_\ell+1)(k_\ell+2),$$ where the numbers $k_\ell\in\{0,\dotsc,c\}$ are distinct. Hence if we define $$s_k:=\begin{cases} 2,&k\in\{k_1,\dotsc,k_m\},\\ 1,&k\notin\{k_1,\dotsc,k_m\}, \end{cases}$$ then we obtain $$a=\sum_{k=0}^c(k+2)^{s_k}.$$