[proofplan] We compute the [probability mass function](/page/Probability%20Mass%20Function) of $N$ directly. For each subset $S\subseteq\{1,\ldots,n\}$, the event that exactly the events indexed by $S$ occur is an intersection of selected $A_i$ and selected complements $A_j^c$. Independence gives the probability of each such event, and the events with $|S|=k$ partition $\{N=k\}$. Summing over the $\binom nk$ possible subsets gives the binomial mass function. [/proofplan]

[step:Compute the probability of any fixed occurrence pattern]Let $I:=\{1,\ldots,n\}$. For a subset $S\subseteq I$, define the event \begin{align*} E_S:=\left(\bigcap_{i\in S}A_i\right)\cap\left(\bigcap_{j\in I\setminus S}A_j^c\right). \end{align*} We claim that \begin{align*} \mathbb P(E_S)=p^{|S|}(1-p)^{n-|S|}. \end{align*} We first justify the use of complements. More generally, let $S,T\subseteq I$ be disjoint, and define \begin{align*} E_{S,T}:=\left(\bigcap_{i\in S}A_i\right)\cap\left(\bigcap_{j\in T}A_j^c\right). \end{align*} We prove by induction on $|T|$ that \begin{align*} \mathbb P(E_{S,T})=p^{|S|}(1-p)^{|T|}. \end{align*} Throughout this induction, an empty intersection is interpreted as $\Omega$ and an empty product as $1$. If $|T|=0$, then $E_{S,T}=\bigcap_{i\in S}A_i$, and independence of $A_1,\ldots,A_n$ gives \begin{align*} \mathbb P(E_{S,T})=\prod_{i\in S}\mathbb P(A_i)=p^{|S|}. \end{align*} Assume the formula holds whenever the complement-index set has size $r$, and let $T$ have size $r+1$. Choose $j_0\in T$ and set $T_0:=T\setminus\{j_0\}$. Then \begin{align*} E_{S,T}=E_{S,T_0}\setminus E_{S\cup\{j_0\},T_0}, \end{align*} and the second event is contained in the first. Therefore finite additivity gives \begin{align*} \mathbb P(E_{S,T})=\mathbb P(E_{S,T_0})-\mathbb P(E_{S\cup\{j_0\},T_0}). \end{align*} The pairs $(S,T_0)$ and $(S\cup\{j_0\},T_0)$ are disjoint pairs of subsets of $I$: this follows from $S\cap T=\varnothing$, $T_0\subseteq T$, and $j_0\notin T_0$. By the induction hypothesis applied to these two pairs, \begin{align*} \mathbb P(E_{S,T})=p^{|S|}(1-p)^r-p^{|S|+1}(1-p)^r. \end{align*} Factoring the right-hand side gives \begin{align*} \mathbb P(E_{S,T})=p^{|S|}(1-p)^{r+1}. \end{align*} This proves the induction. Taking $T=I\setminus S$ gives the claimed formula for $\mathbb P(E_S)$.[/step]

[guided]The only subtle point is that the definition of independence is stated for intersections of the events $A_i$, while the event $E_S$ also contains complements $A_j^c$. We therefore prove explicitly that independence is preserved under replacing some of the events by their complements. Let $S,T\subseteq I$ be disjoint, and define \begin{align*} E_{S,T}:=\left(\bigcap_{i\in S}A_i\right)\cap\left(\bigcap_{j\in T}A_j^c\right). \end{align*} We prove by induction on the number $|T|$ of complements that \begin{align*} \mathbb P(E_{S,T})=p^{|S|}(1-p)^{|T|}. \end{align*} We use the standard conventions that an empty intersection is $\Omega$ and an empty product is $1$; these conventions are needed when $S=\varnothing$ or $T=\varnothing$. When $|T|=0$, there are no complements, so \begin{align*} E_{S,T}=\bigcap_{i\in S}A_i. \end{align*} Since $A_1,\ldots,A_n$ are independent and $\mathbb P(A_i)=p$ for every $i\in I$, the definition of independence gives \begin{align*} \mathbb P(E_{S,T})=\prod_{i\in S}\mathbb P(A_i)=p^{|S|}. \end{align*} This is the desired formula in the base case. Now suppose the formula has been proved whenever $|T|=r$, and let $T$ have size $r+1$. Choose one complement index $j_0\in T$, and set $T_0:=T\setminus\{j_0\}$. The event $E_{S,T}$ is the part of $E_{S,T_0}$ where $A_{j_0}$ does not occur. Equivalently, \begin{align*} E_{S,T}=E_{S,T_0}\setminus E_{S\cup\{j_0\},T_0}. \end{align*} The event $E_{S\cup\{j_0\},T_0}$ is contained in $E_{S,T_0}$, because it imposes all the requirements of $E_{S,T_0}$ and also requires $A_{j_0}$. Hence finite additivity of the [probability measure](/page/Probability%20Measure) gives \begin{align*} \mathbb P(E_{S,T})=\mathbb P(E_{S,T_0})-\mathbb P(E_{S\cup\{j_0\},T_0}). \end{align*} Both terms on the right now have only $r$ complement indices, and the required disjointness conditions still hold. Indeed, $S\cap T_0=\varnothing$ because $T_0\subseteq T$ and $S\cap T=\varnothing$, while $(S\cup\{j_0\})\cap T_0=\varnothing$ because also $j_0\notin T_0$. Therefore the induction hypothesis applies to $(S,T_0)$ and $(S\cup\{j_0\},T_0)$: \begin{align*} \mathbb P(E_{S,T})=p^{|S|}(1-p)^r-p^{|S|+1}(1-p)^r. \end{align*} Factoring gives \begin{align*} \mathbb P(E_{S,T})=p^{|S|}(1-p)^r(1-p)=p^{|S|}(1-p)^{r+1}. \end{align*} This completes the induction. Finally, for a fixed occurrence set $S\subseteq I$, taking $T=I\setminus S$ gives \begin{align*} \mathbb P(E_S)=p^{|S|}(1-p)^{n-|S|}. \end{align*}[/guided]

[step:Partition the event $\{N=k\}$ by the set of indices that occur] Fix $k\in\{0,1,\ldots,n\}$. For each $\omega\in\Omega$, the value $\mathbb{1}_{A_i}(\omega)$ is either $0$ or $1$, so $N(\omega)$ counts the number of indices $i\in I$ for which $\omega\in A_i$. Hence \begin{align*} \{N=k\}=\bigcup_{\substack{S\subseteq I, |S|=k}}E_S. \end{align*} The union is disjoint: if $S\neq S'$, choose an index $i\in I$ that belongs to exactly one of $S$ and $S'$. Then $E_S$ requires exactly one of $\omega\in A_i$ and $\omega\in A_i^c$, while $E_{S'}$ requires the other, so $E_S\cap E_{S'}=\varnothing$. Therefore finite additivity of $\mathbb P$ gives \begin{align*} \mathbb P(N=k)=\sum_{\substack{S\subseteq I, |S|=k}}\mathbb P(E_S). \end{align*} [/step]

[step:Sum the equal probabilities and identify the binomial law] For every subset $S\subseteq I$ with $|S|=k$, the previous computation gives \begin{align*} \mathbb P(E_S)=p^k(1-p)^{n-k}. \end{align*} There are exactly $\binom nk$ subsets of $I$ with cardinality $k$. Hence \begin{align*} \mathbb P(N=k)=\binom nk p^k(1-p)^{n-k}. \end{align*} This holds for every $k\in\{0,1,\ldots,n\}$. Since $N$ takes values in $\{0,1,\ldots,n\}$ and has the probability mass function of the binomial distribution with parameters $n$ and $p$, we conclude that \begin{align*} N\sim\operatorname{Bin}(n,p). \end{align*} [/step]