Proof by induction that $\prod\limits^n_{i=1}(1+x_i)=\sum\limits_{A\subset[n]}\prod\limits_{i\in A} x_i$ holds Consider $x_1,x_2,\ldots,x_n\in \mathbb{Z}$ and $[n]=\{1,2,\ldots,n\}$. Define $\prod\limits_{i\in\varnothing}x_i=1$.
I intend to show that $\prod\limits^n_{i=1}(1+x_i)=\sum\limits_{A\subset[n]}\prod\limits_{i\in A} x_i$ holds for any $n\in\mathbb{N}$.
Proof.
Base case. $n=1$. $\prod\limits^n_{i=1}(1+x_i)=\sum\limits_{A\subset[n]}\prod\limits_{i\in A} x_i \implies \prod\limits^1_{i=1}(1+x_i)=\sum\limits_{A\subset[1]}\prod\limits_{i\in A} x_i$. As $[1]=\{1\}$ has $2$ subsets, $\varnothing$ and $\{1\}$, we have that:
\begin{align*}
    \prod\limits^1_{i=1}(1+x_i)&=\sum\limits_{A\subset[1]}\prod\limits_{i\in A} x_i\\
    1+x_1&=\prod_{i\in \varnothing}x_i + \prod_{i \in \{1\}}x_i\\
    1+x_1&=1 + x_1
\end{align*}
Inductive hypothesis. We will show that if $\prod\limits^n_{i=1}(1+x_i)=\sum\limits_{A\subset[n]}\prod\limits_{i\in A} x_i$ holds for $n$, then it implies that $\prod\limits^{n+1}_{i=1}(1+x_i)=\sum\limits_{A\subset[n+1]}\prod\limits_{i\in A} x_i$ holds for $n+1$.
Inductive step.
At $\prod\limits^n_{i=1}(1+x_i)=\sum\limits_{A\subset[n]}\prod\limits_{i\in A} x_i$, we multiply both sides by $(1+x_{n+1})$ and then we have the following chain of equalities:
\begin{align*}
    \prod^{n+1}_{i=1}(1+x_i)&=(1+x_{n+1})\sum_{A\subset[n]}\prod_{i\in A} x_i\\
    &=\left(\sum_{A\subset[n]}\prod_{i\in A} x_i\right)+x_{n+1}\left(\sum_{A\subset[n]}\prod_{i\in A} x_i\right)\\
    &=\left(\sum_{A\subset[n]}\prod_{i\in A} x_i\right)+\left(\sum_{A\subset[n]}x_{n+1} \prod_{i\in A} x_i\right)\\
\end{align*}
But we have that:
\begin{align*}
   \sum_{A\subset[n]}x_{n+1} \prod_{i\in A} x_i &= \left(\sum_{A\subset[n]\cup \{n+1\}} \prod_{i\in A} x_i\right)-\left(\sum_{A\subset[n]} \prod_{i\in A} x_i\right)\\
   &= \left(\sum_{A\subset[n+1]} \prod_{i\in A} x_i\right)-\left(\sum_{A\subset[n]} \prod_{i\in A} x_i\right)
\end{align*}
Therefore, substituting the above equation in our main equation, we have:
\begin{align*}
    \prod^{n+1}_{i=1}(1+x_i)&=\left(\sum_{A\subset[n]}\prod_{i\in A} x_i\right)+\left(\sum_{A\subset[n]}x_{n+1} \prod_{i\in A} x_i\right)\\
    &=\left(\sum_{A\subset[n]}\prod_{i\in A} x_i\right)+\left(\sum_{A\subset[n+1]} \prod_{i\in A} x_i\right)-\left(\sum_{A\subset[n]} \prod_{i\in A} x_i\right)\\
    &=\left(\sum_{A\subset[n+1]} \prod_{i\in A} x_i\right)
\end{align*}
$\tag*{$\blacksquare$}$
$\rule{10cm}{0.4pt}$
I'm posting this here for the following reasons:

*

*This was the best solution I could get. Is there any simpler way to prove it by induction?

*The step where I substitute $\sum_{A\subset[n]}x_{n+1} \prod_{i\in A} x_i$ for $\left(\sum_{A\subset[n+1]} \prod_{i\in A} x_i\right)-\left(\sum_{A\subset[n]} \prod_{i\in A} x_i\right)$ seems a little too magical. I know it's true, I've seen it work. Do I need to prove it? If yes, any hints how to do it?

 A: I would modify the notation slightly as follows.  Define $\mathcal P(S)$ to be the power set of $S$.  That is to say, the elements of $\mathcal P(S)$ are all possible subsets of $S$, including $S$ itself and the empty set $\varnothing$.  If $[n+1] = \{1, 2, \ldots, n, n+1\}$, then we may partition $\mathcal P([n+1])$ into subsets $N$, $N'$, depending on whether the subset contains $n+1$.  That is to say, $$N = \{X \in \mathcal P([n+1]) : n+1 \notin X \}, \\ N' = \{X \in \mathcal P([n+1]) : n+1 \in X\}.$$  Then by this criterion, $N = \mathcal P([n])$, the power set of $[n]$, because every subset not containing $n+1$ is a subset of $[n]$, and every subset of $[n]$ does not contain $n+1$.  The key insight is to observe that there is a natural bijection between the elements of $N$ and $N'$, specifically, $$f : N \leftrightarrow N', \quad f(X) = X \cup \{n+1\}.$$  That is to say, each element $X \in N$ maps uniquely to an element of $N'$ by attaching $n+1$ to $X$, and the reverse mapping involves removing $n+1$ from $N'$.
All this is background material to proceed with the basic proof:  if we define $$P_n = \prod_{i=1}^n (1 + x_i), \quad m(X) = \prod_{i \in X} x_i,$$ and $$S_n = \sum_{X \in \mathcal P([n])} m(X),$$ which is equivalent to your expression, we clearly have $$\begin{align}
S_{n+1} &= \sum_{X \in \mathcal P([n+1])} m(X) \\
&= \sum_{X \in (N \cup N')} m(X) \\
&= \sum_{X \in N} m(X) + \sum_{X \in N'} m(X) \\
&= \sum_{X \in N} m(X) + \sum_{X \in N} x_{n+1} m(X) \\
&= \sum_{X \in N} m(X) + x_{n+1} \sum_{X \in N} m(X) \\
&= (1 + x_{n+1}) \sum_{X \in N} m(X) \\
&= (1 + x_{n+1}) \sum_{X \in \mathcal P([n])} m(X) \\
&= (1 + x_{n+1}) P_n \\
&= P_{n+1}.
\end{align}$$
This completes the induction step, where in the second to last equality, we used the induction hypothesis $P_n = S_n$.
