# $X,Y$ discrete independent random variables, then $\sum\limits_{k=0}^n P(X=n-k)P(Y=k) = \sum\limits_{k=0}^n P(X=n-k,Y=k)$

Let $X,Y$ be discrete independent random variables with $X,Y \geq 0$. Then $$P(X+Y=n) = \underset{k=0}{\overset{n}{\sum}} P(X=n-k)P(Y=k).$$

(I am sure this is very very easy and I am just overlooking something very simple)

$\textbf{Proof:}$ Trying to show right hand side is the same as left hand side.

$$\sum_{k=0}^n P(X=n-k)P(Y=k) = \sum_{k=0}^n P(X=n-k,Y=k)$$ since $X,Y$ independent, (At this point I am just trying things to see if I can get the conclusion) $$= \sum_{k=0}^n P(X+Y=n,Y=k)$$ $$= \sum_{k=0}^n P(X+k=n)$$ $$= P(X=n) + P(X=n-1)+ \cdots +P(X=0)$$ $$= F_X(n)$$

Could anyone help with this?

*Thank you for your responding André and Dilip.

It is very clear now.

-
You are assuming that $X$ and $Y$ take on only integer values? – Dilip Sarwate Nov 30 '12 at 3:00
Yes, specifically related to a problem that this result will help me with, $X,Y = \{ 0,1,2,... \}$. I am not sure of the exact conditions where this would hold, but at the least, $X,Y$ like $X,Y = \{ 0,1,2,... \}$. – Frudrururu Nov 30 '12 at 3:01
OK. What is the definition of independent random variables? Can the definition be used to decide whether $P\{X = m, Y = n\}$ is greater than, smaller than, or equal $P\{X=m\}P\{Y=n\}$? – Dilip Sarwate Nov 30 '12 at 3:05
@John : I changed \underset\sum\limits_{k=0}{\overset{n}{\sum}} to \sum_{k=0}^n in several cases. In a "displayed" setting, this is rendered as $\displaystyle\sum_{k=0}^n$ and in an "inline" setting it appears as $\sum_{k=0}^n$. In your title, I wrote \sum\limits_{k=0}^n to make it appear as in a "displayed" setting, that being what you appeared to have intended. TeX is sophisticated. – Michael Hardy Nov 30 '12 at 3:54
Ok thank you, I will remember this for the future ;) – Frudrururu Nov 30 '12 at 3:55

We need more, for the result as it is stated. We need to assume that $X$ and $Y$ can only take on non-negative integer values.

If this is the case, how could $X+Y=n$?

We could have $X=n$ and $Y=0$. By independence, the probability that $X=n$ and $Y=0$ is $\Pr(X=n)\Pr(Y=0)$.

We could have $X=n-1$ and $Y=1$. By independence, the probability that $X=n-1$ and $Y=1$ is $\Pr(X=n-1)\Pr(Y=1)$.

We could have $X=n-2$ and $Y=2$. By independence, the probability that $X=n-2$ and $Y=2$ is $\Pr(X=n-2)\Pr(Y=2)$.

And so on!

Finally, we could have $X=0$ and $Y=n$. By independence, the probability that $X=0$ and $Y=n$ is $\Pr(X=0)\Pr(Y=n)$.

The above events are (pairwise) disjoint, and they are the only way we can have $X+Y=n$. So to find $\Pr(X+Y=n)$, we need to add up all the above probabilities. That's exactly what the formula $$\Pr(X+Y=n)=\sum_{k=0}^n \Pr(X=n-k)\Pr(X=k)$$ says.

-
Ok very clear thank you. – Frudrururu Nov 30 '12 at 3:28