Consider all non-empty subsets of $\{1, 2, \ldots, n\}$ having no consecutive elements. Prove that sum of squares of products of these subsets equals $(n + 1)! − 1$: i.e. if $\mathcal{C}_n$ is the set of all such subsets, $$ \sum_{J\in\mathcal{C}_n}\left(\prod_{i\in J}i\right)^2 = (n+1)!-1. $$ Note that if we were to include the empty set in $\mathcal{C}_n$ and define the product for this to be $1$, the sum would be $(n+1)!$ instead.
2026-04-03 04:24:16.1775190256
Showing sum of squares of products of all non-empty subsets of $\{1, 2, 3, \ldots, n\}$ having no consecutive elements is $(n + 1)! − 1$
1.8k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
Let $\mathcal{C}^*_n=\mathcal{C}_n\cup\{\{\}\}$ consist of all subsets of $\{1,\ldots,n\}$ with no two consecutive elements, including the empty set: i.e. $J\in\mathcal{C}^*_n$ if $J\in\{1,\ldots,n\}$ and there is no $i$ so that $i\in J$ and $i+1\in J$. Now, let $$ S_n=\sum_{J\in\mathcal{C}^*_n}\left(\prod_{i\in J}i\right)^2 $$ where $\prod_{i\in\{\}}i=1$ for the empty set. We wish to prove that $S_n=(n+1)!$. To get the original problem, remove the empty set from the sum which corresponds to subtracting $1$.
For $n=0,1$, it's easy to check that $S_n=(n+1)!$. So next, we do induction on $n$.
Assuming $S_k=(k+1)!$ for $k<n$, we split the sets of $\mathcal{C}^*_n$ into those that contain $n$ and those that do not. The elements that do not contain $n$ are those of $\mathcal{C}^*_{n-1}$; the elements that contain $n$ correspond to $J\cup\{n\}$ where $J\in\mathcal{C}^*_{n-2}$. Thus, we get $$ S_n =\sum_{J\in\mathcal{C}^*_{n-1}}\left(\prod_{j\in J}j\right)^2 +\sum_{J\in\mathcal{C}^*_{n-2}}\left(n\cdot\prod_{j\in J}j\right)^2 $$ which gives us $S_n$ expressed in terms of $S_{n-1}$ and $S_{n-2}$: $$ S_n=S_{n-1}+n^2\cdot S_{n-2}=n!+n^2\cdot(n-1)!=(n+1)! $$ or $(n+1)!-1$ if we remove the empty set and sum over $\mathcal{C}_n$ instead.