Sum of squares of products of subsets without neighboring elements equals $(N+1)! -1$ Question: Let $n$ be any natural number. Consider all nonempty subsets of the set $\{1,2,...,n\}$, which do not contain any neighboring elements. Prove that the sum of the squares of the products of all numbers in these subsets is $$(n + 1)! - 1.$$ For example, if $n = 3$, then such subsets of $\{1,2,3\}$ are $\{1\}$, $\{2\}$, $\{3\}$, and $\{1,3\}$, and $$1^2 + 2^2 + 3^2 + (1\cdot3)^2 = 23 = 4! -1.$$
This question can be proved by induction, as shown here:
induction (sum of squares of products of elements of certain subsets of $\{1,\dots,n\}$)
This seems to me like something that is really out of the blue. So my question is, is there another way to see why this is true? Such as a combinatorial argument. In particular, does the quantity "sum of squares of products of numbers in subsets without neighboring elements" arise in some natural way?
 A: Let's say that $S \subset \{1, \dots, n\}$ is sparse if it doesn't contain any neighboring elements. Note that $S$ is sparse if and only if $S$ and $S-1$ are disjoint, where $S-1 = \{a-1 \mid a \in S\}$ (excluding $0$ if necessary). I'll consider $\varnothing$ to be a sparse subset with $\prod_{a \in \varnothing} a^2 = 1$, so that now we want to show that $\sum_S \prod_{a \in S} a^2 = (n+1)!$, where the sum is taken over all sparse $S \subset \{1, \dots, n\}$. Then for a sparse $S$ we have 
$$\prod_{a \in S} a^2 
= \prod_{a \in S} a ((a-1) + 1)
= \prod_{a \in S} a \prod_{b \in S-1} (b+1)
= \prod_{a \in S} a \sum_{T' \subset S-1} \prod_{b \in T'} b
= \sum_{T' \subset S-1} \prod_{a \in S \cup T'} a.$$
Proposition. For a set $T \subset \{1, \dots, n\}$, we can uniquely write $T = S \cup T'$ for $S$ sparse and $T' \subset S-1$. 
Proof: For $a \in T$, let 
$$\ell(a) = \max \{k \geq 0 \mid \{a, a+1, \dots, a + k\} \subset T\}.$$ 
I'll show that the above holds iff $S = \{a \in T \mid \ell(a) \text{ is even}\}$. First suppose $S$ is this set. Then for $a \in S$, if $a-1 \in T$, $\ell(a-1) = \ell(a) + 1$ is odd, and otherwise $a-1 \not \in T$, so either way $a-1 \not \in S$, hence $S$ is sparse. Furthermore $T \setminus S$ consists of those points $a$ with $\ell(a)$ odd, each of which must then have $a+1 \in S$, so $T' := T \setminus S \subset S-1$. Conversely, suppose $T = S \cup T'$ for $S$ sparse and $T' \subset S-1$. Then a brief induction on $\ell(a)$ shows that $a \in S$ iff $\ell(a)$ is even: when $\ell(a) = 0$, $a \in S$, and when $\ell(a) = 1$, $a \in T'$. For $\ell(a) \geq 2$, either $a \in S$, in which case $a+1 \in T'$ by sparsity of $S$, so $\ell(a+1) = \ell(a) - 1$ is odd, hence $\ell(a)$ is even, or in the other case $a \in T'$, so $a+1 \in S$, $\ell(a+1) = \ell(a) - 1$ is even, hence $\ell(a)$ is odd. Thus $S = \{a \in T \mid \ell(a) \text{ is even}\}$.
Letting $s(T)$ be the unique $S$ described above, we have that the sets $T$ with $s(T) = S$ are exactly those with $T = S \cup T'$ for $T' \subset S-1$. Then using the above, we have 
$$\prod_{a \in S} a^2 = \sum_{s(T) = S} \prod_{a \in T} a$$
so it follows that 
$$\sum_{S \text{ sparse}} \prod_{a \in S} a^2 = \sum_{S \text{ sparse}} \sum_{s(T) = S} \prod_{a \in T} a = \sum_{T \subset \{1, \dots, n\}} \prod_{a \in T} a = \prod_{a \in \{1, \dots, n\}} (a + 1) = (n+1)!.$$
A: This is a little bit sketchy.
Consider the easier problem of finding the sum of the squares of the products of all elements for each subset of $\{1,2,3,...,n\}$ (so I am dropping the neighboring condition).
The answer is
$$(1+1^2)(1+2^2)(1+3^2)...(1+n^2)$$
This product can be written as a sum where each term is obtained by choosing $1$ or $j^2$ for each $(1+j^2)$ and then muliplying everything.
In fact, each term obtained this way is the square of the products of all elements of a particular subset.
For example, if we pick $1^2$ in $(1+1^2)$, $5^2$ in $(1+5^2)$, $11^2$ in $(1+11^2)$ and $1$ in all other terms of the product we get the square of the products of all elements of $\{1,5,11\}$.  
Now I try to adapt this approach to the actual problem.
Consider the following sum:
$$\left(1+\frac{n^2}{n}\right)\left(1+\frac{(n-1)^2}{n-1}\right)\left(1+\frac{(n-2)^2}{n-2}\right)...\left(1+\frac{2^2}{2}\right)(1+1^2) \tag{1}$$ 
We start from the term $\left(1+\frac{n^2}{n}\right)$. We can decide to not include $n$ in our subset, hence we pick $1$ in the term $\left(1+\frac{n^2}{n}\right)$ and the next term we are going to consider is $\left(1+\frac{(n-1)^2}{n-1}\right)$.
Or, we can include $n$, hence we pick $\frac{n^2}{n}$ in the term $\left(1+\frac{n^2}{n}\right)$. In this case, we are multypling by $n^2$ (for the same reason as before) and we are dividing by $n$; notice that the term $\left(1+\frac{(n-1)^2}{n-1}\right)$ is exactly equal to $n$, so by dividing by $n$ we are cancelling $\left(1+\frac{(n-1)^2}{n-1}\right)$; hence, the next term we are going to consider next is $\left(1+\frac{(n-2)^2}{n-2}\right)$.  
The idea is that if we include $n$ in our subset we cannot include $n-1$ (beacuse otherwise we would have two neighboring elements); cancelling the term $\left(1+\frac{(n-1)^2}{n-1}\right)$ is the same as not picking $n-1$.
We then repeat and the final result should be the square of the product of all elements for a subset of $\{1,2,3,...,n\}$ with no neighboring elements.
For example, consider the subset $\{13,5,3\}$; this corresponds to the term:
$$\frac{13^2}{13}\left(1+\frac{12^2}{12}\right)\frac{5^2}{5}\left(1+\frac{4^2}{4}\right)\frac{3^2}{3}\left(1+\frac{2^2}{2}\right)$$
$$=\frac{13^2}{13}(13)\frac{5^2}{5}\left(5\right)\frac{3^2}{3}\left(3\right)$$
$$=13*5*3$$
Notice that (1) is equal to $(n+1)!$ so this should be the value of the required sum.
