Problem. (AoPS) For any positive integers $k,m$, let $S_k(m)$ be the number $n\in \{1,...,2^k\}$ which can be expressed as $$n = \sum_{i=0}^k \varepsilon_i\cdot 2^i\qquad \varepsilon_i\in \{-1,0,1\}$$ in exactly $m$ different ways. Show that $S_k(m) = \varphi(m)$ for all sufficiently large $k$.

Remarks. Straight up, I basically had no idea how something like combinations of a sum can be related to $\varphi(m)$ at all (that’s part of the appeal I guess).

So what I should have started off with is to list all the small distributions (i.e. find $S_k$ for small $k$), but alas, I’m lazy and have all the time in the world.

First thing I thought was that probably small numbers will be able to be represented in many different ways (this is not quite true, but bear with me), so I started thinking about $2^k$ and like $(2^k-s)$ for small $s$. I didn’t get very far, but I realized that you can kind of compose $\sum_{i=0}^{k'}\varepsilon_i\cdot 2^i$ and $\sum_{i=k'+1}^k\varepsilon_i \cdot 2^i$ to get many different sums (and of course in hindsight I know this is completely off, but eh).

Then first nontrivial realization is: oh if we’re only thinking about $\{1,...,2^k\}$, then really the $\varepsilon_k$ term is kinda fixed by the previous values of $\varepsilon_i$. This made me think about recursion: if we know $S_{k-1}$, we can figure out what $S_k$ is just by pasting it a few times … but actually that’s not completely true because we need to know what the distribution beyond $2^{k-1}$ is. But we manage, because that means we must have selected $2^{k-1}$ (i.e. $\varepsilon_{k-1} = 1$) and so we’re dealing with an even smaller copy $S_{k-2}$ and so on.

But that’s not so easy to think about (when we want to consider “count”), so I go to bed.

When I’m taking a shower the next morning, I realize that there’s another way to do recursion: instead of adding on the next $\varepsilon_k\cdot 2^k$ term, we could have just multiplied by two and added $\varepsilon_0$! This makes the restriction onto $\{1,2,...,2^k\}$ way easier to think about.

So what’s the recursion rule? It’s something like $$a'_{2i},a'_{2i+1},a'_{2i+2} \leftarrow a_i, a_{i+1}$$ and at this point I basically know where the $\varphi(m)$ comes from and call it a day.

Here’s a hint if you haven’t figured it out: take two sequences starting with $a_0=0,a_1=1$ and $b_0=1,b_1=1$. In particular, write the $\{a\}$ sequence directly above the $\{b\}$ one, and keep applying the recursive rule. Do you see anything interesting?

Misc. The first iteration of the problem was actually wrong, so I coded it up to check if the proposed change was actually right:

def construct_list(N):
  if N == 0:
    return [0]
  else:
    prev = construct_list(N-1)
    return prev+[x+2 ** N for x in prev] + [x-2**N for x in prev]

def get_counts(sumlist, n):
  #m = min(sumlist)
  #M = max(sumlist)
  m = 1
  M = 2 ** n
  return [sumlist.count(x) for x in range(m, M+1)]

def thing(N):
  MAX = 12
  results = []
  for n in range(MAX):
    results.append(get_counts(construct_list(n), n).count(N))
  print(N,": ",results)

for i in range(1,16):
  thing(i)