The problem devised by Ginger Bolton and published in the January 1989 issue of College Mathematics Journal (vol. 20, no. 1, p. 68).
Given a positive integer $n \ge 2$, let $S$ be the set of all nonempty subsets of $\{2,3,...,n\}$. For each $S_i\in S$, let $P_i$ be the product of the elements of $S_i$.
Prove that $\sum_{i=1}^{2^{n-1}-1} P_i = \frac{(n+1)!}{2}-1$
I'll show my attempt to prove it which I'm not sure is correct, the question is in the end.
I was trying to prove that with mathematical induction, with the property
$Q(n): \sum_{i=1}^{2^{n-1}-1} P_i = \frac{(n+1)!}{2}-1$.
It holds for the base case $n = 2$.
Now I need to prove $Q(k) \rightarrow Q(k+1)$, that is to show that
$\sum_{i=1}^{2^{k}-1} P_i = \frac{(k+2)!}{2}-1$
To prove that, I observe that the subsets of $\{2,3,...,k,k+1\}$ either contain $k+1$ or not. Those that don't contain $k+1$ are subsets of $\{2,3,...,k\}$, for which the inductive hypothesis holds.
Now for each subset $X$ that doesn't contain $k+1$ there is a counterpart $X \cup \{k+1\} \subseteq \{2,3,...,k,k+1\}$. Also note that the number of subsets that don't have $k+1$ and those that have it is equal.
Let $s_{k+1}$ be the sum of products of the elements of subsets of a set with cardinality $k+1$. Then
$s_{k+1} = s_k + (k+1)s_k + (k+1)$
The right part of this equation is:
the sum for the subsets without $(k+1)$ + the sum for the subsets with $(k+1)$ + $\emptyset \cup (k+1)$.
Substituting the right part of the inductive hypothesis into the equation I get
$s_{k+1} = s_k + (k+1)s_k + k = \bigl( \frac{(k+1)!}{2}-1 \bigr) + (k+1)\bigl( \frac{(k+1)!}{2}-1 \bigr) + (k+1)$ = (some algebra) = $\frac{(k+2)!}{2}-1$
Thus I have made a conjecture of what the sum for a set of cardinality $k+1$ must be and shown that it indeed equals to the right part of the equation from the conclusion of the inductive step.
But what about the conclusion's left part? Do I need to show that $s_{k+1} = \sum_{i=1}^{2^{k}-1} P_i$ to complete the proof?
For any $A$, we have $$\sum_{\substack{S \subseteq A:\\S \not= \emptyset\\}} \prod_{j \in S} j=\prod_{j \in A} (1+j) - 1.$$ In particular, $A=\{2,\dots,n\}$ yields $$\sum_{\substack{S \subseteq \{2,\dots,n\}:\\S \not= \emptyset\\}} \prod_{j \in S} j=\prod_{j \in \{2,\dots,n\}} (1+j) - 1=\frac{1}{2}\prod_{j =1}^n\ (1+j)-1=\frac{(n+1)!}{2}-1.$$