number theory - Induction on a double summation

Let $f_1, \ldots, f_k, \ldots$ be arbitrary real numbers. Prove that for each non-negative integer $k$:

$\left (1-f_{1} \right )...\left (1-f_{k} \right ) = \sum_{j=0}^{k}(-1)^{j} \sum_{i_{1}

Hint: Use induction on $k$. You may assume that empty products are $1$. In the case
that the $f_{i}$ are indicator functions of sets this is the “inclusion–exclusion principle”, “principle of cross classification” or “sieve principle”, depending on one’s point
of view.

---

So far I have been able to prove the base case where $k = 1$, and assumed the inductive hypothesis where$k = n$. I am unsure how to go about proving that this holds for the $k = n + 1$ step.

Any help would be really appreciated.

Answer

Divide outer sum in RHS for $k=n+1$ into two parts: summands with $f_{n+1}$ and summands without. Now try to establish connection of these parts with RHS for $n=k$.

Let's denote RHS by $S(k)$. Then sum of terms in $S(n+1)$ without $f_{n+1}$ is $S(n)$. And sum of other terms is equals to

$$\sum_{j=1}^{n+1} (-1)^j \sum_{i_1 < \ldots < i_{j-1} < i_j = n+1} f_{i_1}\cdot \ldots \cdot f_{i_{j-1}}\cdot f_{n+1} = \sum_{j=0}^{n} (-1)^{j+1} f_{n+1}\sum_{i_1 < \ldots < i_{j}} f_{i_1}\cdot \ldots \cdot f_{i_{j}},$$
it's exactly $-f_{n+1}\cdot S(n)$.