Conjecture:
Given any $n \in \mathbb{Z}_{\geq 0}$, we have $$|\{S : (S \subseteq [0,n]) \land (n, n-1 \not \in S+S)\}| = F(n+2),$$ where $F$, the sequence of Fibonacci numbers, is given by $F(j) = F(j-1) + F(j-2)$, with $F(0) = 0$ and $F(1)=1$.
A program verifies this conjecture for small $n$. Is it true for all $n$?
A few notes on notation:
This is always true. The integers $[0,n]$ can be rearranged as $$n, 0, n-1, 1, n-2, 2, ...$$
You'll notice that two numbers in the interval sum to $n$ or $n-1$ precisely when they are adjacent in the list! This reduces the question to the classic counting problem of how many subsets of $[1,n]$ have no two consecutive members, which is described in more detail here.
The solution seems a bit arbitrary so I'll try to explain how I thought it up. Generally when wanting to show that one sequence equals another you want to use the other's simplest properties and progressively use more complex ones as those fail. In this case, the simplest property is that they are recursive in a way that allows them to apply in that classic problem. The idea of avoiding things and Fibonacci led me to start thinking about making a connection to that problem, and in this case it worked out.
