[proofplan] Fix an integer $k$ and decompose the event $\{X+Y=k\}$ according to the value taken by $X$. This gives a countable disjoint union of events $\{X=j\}\cap\{Y=k-j\}$ indexed by $j\in\mathbb Z$. Countable additivity turns the probability of the union into a sum, and independence factors each joint probability into the product of the two marginal probabilities. [/proofplan]

[step:Decompose the event $\{X+Y=k\}$ by the value of $X$]Fix $k \in \mathbb Z$. Define the map $S: \Omega \to \mathbb Z$ by $S(\omega)=X(\omega)+Y(\omega)$ for $\omega\in\Omega$. Since $X$ and $Y$ take values in $\mathbb Z$, the map $S$ is integer-valued. For each $j \in \mathbb Z$, define the event \begin{align*} A_j := \{\omega \in \Omega : X(\omega)=j\} \cap \{\omega \in \Omega : Y(\omega)=k-j\}. \end{align*} Then \begin{align*} \{\omega \in \Omega : X(\omega)+Y(\omega)=k\} = \bigcup_{j\in\mathbb Z} A_j. \end{align*} Indeed, if $X(\omega)+Y(\omega)=k$, then with $j=X(\omega)$ we have $\omega \in A_j$. Conversely, if $\omega \in A_j$ for some $j \in \mathbb Z$, then $X(\omega)+Y(\omega)=j+(k-j)=k$. The events $(A_j)_{j\in\mathbb Z}$ are pairwise disjoint. If $j_1,j_2\in\mathbb Z$ with $j_1\neq j_2$, then no $\omega\in\Omega$ can satisfy both $X(\omega)=j_1$ and $X(\omega)=j_2$, so $A_{j_1}\cap A_{j_2}=\varnothing$. The displayed decomposition also proves measurability of $S$. Indeed, each $A_j$ belongs to $\mathcal F$ because $X$ and $Y$ are measurable and $\{j\},\{k-j\}\subset\mathbb Z$ belong to $2^{\mathbb Z}$. Hence $S^{-1}(\{k\})=\bigcup_{j\in\mathbb Z}A_j$ belongs to $\mathcal F$ by countable closure of $\mathcal F$. Since $k\in\mathbb Z$ was arbitrary and every subset of $\mathbb Z$ is a countable union of singletons, $S^{-1}(B)\in\mathcal F$ for every $B\subset\mathbb Z$. Thus $S=X+Y:(\Omega,\mathcal F)\to(\mathbb Z,2^{\mathbb Z})$ is a [random variable](/page/Random%20Variable).[/step]

[guided]We fix one target value $k \in \mathbb Z$ and ask: when does $X+Y$ equal $k$? Since $X$ is integer-valued, each outcome $\omega$ with $X(\omega)+Y(\omega)=k$ has a unique integer value $j=X(\omega)$. Once that value of $X$ is fixed, the value of $Y$ is forced to be $k-j$. For each $j \in \mathbb Z$, define \begin{align*} A_j := \{\omega \in \Omega : X(\omega)=j\} \cap \{\omega \in \Omega : Y(\omega)=k-j\}. \end{align*} These events record the mutually exclusive ways in which the sum can equal $k$: first $X$ takes the value $j$, and then $Y$ takes the complementary value $k-j$. We verify the decomposition in both directions. If $\omega \in \Omega$ satisfies $X(\omega)+Y(\omega)=k$, define $j:=X(\omega)$. Because $X$ is integer-valued, $j\in\mathbb Z$, and then $Y(\omega)=k-X(\omega)=k-j$. Hence $\omega\in A_j$, so $\omega$ lies in the union $\bigcup_{j\in\mathbb Z}A_j$. Conversely, if $\omega\in A_j$ for some $j\in\mathbb Z$, then $X(\omega)=j$ and $Y(\omega)=k-j$. Therefore \begin{align*} X(\omega)+Y(\omega)=j+(k-j)=k. \end{align*} Thus \begin{align*} \{\omega \in \Omega : X(\omega)+Y(\omega)=k\} = \bigcup_{j\in\mathbb Z} A_j. \end{align*} Finally, this union is disjoint. If $j_1\neq j_2$, then an outcome $\omega$ cannot simultaneously satisfy $X(\omega)=j_1$ and $X(\omega)=j_2$. Hence $A_{j_1}\cap A_{j_2}=\varnothing$. We also need to justify that $X+Y$ is a random variable, not merely an integer-valued function. For the fixed $k$, the decomposition gives \begin{align*} S^{-1}(\{k\})=\bigcup_{j\in\mathbb Z}A_j. \end{align*} Each $A_j$ is measurable because $A_j=X^{-1}(\{j\})\cap Y^{-1}(\{k-j\})$, the singletons $\{j\}$ and $\{k-j\}$ belong to $2^{\mathbb Z}$, and $X,Y$ are measurable. Since $\mathbb Z$ is countable, the union is countable, so $S^{-1}(\{k\})\in\mathcal F$. Because every subset of $\mathbb Z$ is a countable union of singletons, this proves $S^{-1}(B)\in\mathcal F$ for every $B\subset\mathbb Z$. Therefore $S=X+Y:(\Omega,\mathcal F)\to(\mathbb Z,2^{\mathbb Z})$ is a random variable. The disjointness is exactly what allows countable additivity to convert the probability of the union into a sum of probabilities.[/guided]

[step:Apply countable additivity to the disjoint decomposition] Since $\mathbb Z$ is countable and the events $(A_j)_{j\in\mathbb Z}$ are pairwise disjoint, countable additivity of $\mathbb P$ gives \begin{align*}\mathbb P(X+Y=k)=\sum_{j\in\mathbb Z}\mathbb P(A_j).\end{align*} The series is well-defined as an extended nonnegative series. Moreover its value is bounded above by $1$, because it equals the probability of the event $\{X+Y=k\}$. [/step]

[step:Use independence to factor each joint probability] For each $j\in\mathbb Z$, the events $\{X=j\}$ and $\{Y=k-j\}$ are independent because the random variables $X$ and $Y$ are independent. Therefore \begin{align*}\mathbb P(A_j)=\mathbb P(X=j)\mathbb P(Y=k-j).\end{align*} By the definitions of $p_X$ and $p_Y$, this becomes \begin{align*}\mathbb P(A_j)=p_X(j)p_Y(k-j).\end{align*} Substituting this identity into the countable-additivity formula yields \begin{align*}\mathbb P(X+Y=k)=\sum_{j\in\mathbb Z}p_X(j)p_Y(k-j).\end{align*} [/step]

[step:Identify the resulting formula as the probability mass function of $X+Y$] Define $p_{X+Y}: \mathbb Z \to [0,1]$ by \begin{align*}p_{X+Y}(k)=\mathbb P(X+Y=k).\end{align*} The preceding computation holds for every fixed $k\in\mathbb Z$, so for every $k\in\mathbb Z$, \begin{align*}p_{X+Y}(k)=\sum_{j\in\mathbb Z}p_X(j)p_Y(k-j).\end{align*} This proves the stated convolution formula for the [probability mass function](/page/Probability%20Mass%20Function) of $X+Y$. [/step]