<s>[INST] Sums of powers of two.. with one restriction. For a positive integer $n,$ let $a_n$ denote the number of ways of representing $n$ as a sum of powers of 2, where each power of 2 appears at most three times, and the order of the terms does not matter. For example, $a_8 = 5$ because of the representations
\begin{align*}
8 &= 8 \\
&= 4 + 4 \\
&= 4 + 2 + 2 \\
&= 4 + 2 + 1 + 1 \\
&= 2 + 2 + 2 + 1 + 1.
\end{align*}(The representation $1 + 2 + 1 + 4$ is the same as $4 + 2 + 1 + 1.$) Compute $a_{1000}.$
 [/INST] Let's prove @Oldnboy's conjecture with a hint by @JyrkiLahtonen to a technique the OP might not know well. Restate $n=\sum_jc_j2^j$, with $0\le c_j\le3$, as $x^n=\prod_jx^{c_j2^j}$, so $a_n$ is the $x^n$ coefficient in$$\begin{align}\prod_{j\ge0}(1+x^{2^j}+x^{2\cdot2^j}+x^{3\cdot2^j})&=\prod_j\frac{1-x^{4\cdot2^j}}{1-x^{2^j}}\\&=\frac{1}{(1-x)(1-x^2)}\\&=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots).\end{align}$$This is just the number of integers from $0$ to $n$ inclusive with $n$'s parity, i.e. $\lfloor\tfrac{n}{2}\rfloor+1$ as claimed.
We can use this technique if $3$ is replaced with another Mersenne number. Otherwise, it's a bit tricky because the product doesn't telescope. I've asked a question about further generalization.
</s>