How to compute $\sum^k_{i=0}{k\choose i}\frac{\prod_{j=0}^{i-1}(x+jm)\prod_{j=0}^{k-i-1}(y+jm)}{\prod_{j=0}^{k-1}(x+y+jm)}$? This basic course on probability and statistics is the first course where I feel like a total idiot... especially since I've already forgotten much from the basic courses at discrete mathematics and analysis. Sigh...
The task from a former test:

A HDD contains $x+y$ infected programs; $x$ are infected by malware $X$ and $y$ are infected by malware $Y$. The user runs random programs. Each time a program infected by malware $X$ is run $m$ uninfected programs become infected by malware $X$; same for malware $Y$. Compute the probability that when the $k$th infected program is run it is infected by malware $X$.

Let $X_1=1$  iff the first infected program is infected by $X$, similary let's define $Y_1$, $X_2$, etc.
We have:
$\operatorname{P}(X_1)=\frac{x}{x+y}$
$\operatorname{P}(Y_1)=\frac{y}{x+y}$
$\operatorname{P}(X_2)=\operatorname{P}(X_1)\operatorname{P}(X_2|X_1)+\operatorname{P}(Y_1)\operatorname{P}(X_2|Y_1)=\frac{x}{x+y}\frac{x+m}{x+m+y}+\frac{y}{x+y}\frac{x}{x+y+m}$
$P(Y_2)=\operatorname{P}(X_1)\operatorname{P}(Y_2|X_1)+\operatorname{P}(Y_1)\operatorname{P}(Y_2|Y_1)=\frac{x}{x+y}\frac{y}{x+m+y}+\frac{y}{x+y}\frac{y+m}{x+y+m}$
$\operatorname{P}(X_3)=\frac{x}{x+y}\frac{x+m}{x+m+y}\frac{x+2m}{x+2m+y}+\frac{y}{x+y}\frac{x}{x+y+m}\frac{x+m}{x+m+y+m}+\frac{x}{x+y}\frac{y}{x+m+y}\frac{x+m}{x+m+y+m}+\frac{y}{y+m}\frac{y+m}{x+y+m}+\frac{x}{x+y+2m}$
More generally:
$\operatorname{P}(X_k)=\sum^k_{i=0}{k\choose i}\frac{\prod_{j=0}^{i-1}(x+jm)\prod_{j=0}^{k-i-1}(y+jm)}{\prod_{j=0}^{k-1}(x+y+jm)}$
This is madness for me. That's not even binomial theorem, albeit it's a little bit similar.
Am I doing something wrong? Or how am I supposed to get a closed formula from this sum?
 A: I think that you made a small error in the general formula. Fixing this and expanding the binomial coefficient, we observe that:
\begin{align*}
P(X_{k})&=\sum_{i=0}^{k-1}\mathbb{P}(X_{k}|X_{j}\text{ for }i\text{ values }j\in\{1,\ldots,k-1\})\mathbb{P}(X_{j}\text{ for }i\text{ values }j\in\{1,\ldots,k-1\})\\
&=\sum_{i=0}^{k-1}\binom{k-1}{i}\frac{\prod_{j=0}^{i}(x+jm)\prod_{\ell=0}^{k-1-i}(y+\ell m)}{\prod_{j=0}^{k-1}(x+y+jm)}\\
&=\binom{k-1}{0}\frac{\prod_{\ell=0}^{k-1}(y+\ell m)}{\prod_{j=0}^{k-1}(x+y+jm)}\\&\quad+\sum_{i=1}^{k-1}\left[\binom{k-2}{i-1}+\binom{k-2}{i}\right]\frac{\prod_{j=0}^{i}(x+jm)\prod_{\ell=0}^{k-1-i}(y+\ell m)}{\prod_{j=0}^{k-1}(x+y+jm)}\\
&=\sum_{i=0}^{k-2}\binom{k-2}{i}\left[\frac{\prod_{j=0}^{i}(x+jm)\prod_{\ell=0}^{k-1-i}(y+\ell m)}{\prod_{j=0}^{k-1}(x+y+jm)}+\frac{\prod_{j=0}^{i+1}(x+jm)\prod_{\ell=0}^{k-2-i}(y+\ell m)}{\prod_{j=0}^{k-1}(x+y+jm)}\right]\\
&=\sum_{i=0}^{k-2}\binom{k-2}{i}\frac{\left[\prod_{j=0}^{i}(x+jm)\prod_{\ell=0}^{k-2-i}(y+\ell m)\right]((y+(k-1-i)m)+(x+(i+1)m))}{\prod_{j=0}^{k-1}(x+y+jm)}\\
&=\sum_{i=0}^{k-2}\binom{k-2}{i}\frac{\left[\prod_{j=0}^{i}(x+jm)\prod_{\ell=0}^{k-2-i}(y+\ell m)\right](x+y+(k-1)m)}{\prod_{j=0}^{k-1}(x+y+jm)}\\
&=\sum_{i=0}^{k-2}\binom{k-2}{i}\frac{\prod_{j=0}^{i}(x+jm)\prod_{\ell=0}^{k-2-i}(y+\ell m)}{\prod_{j=0}^{k-2}(x+y+jm)}\\
&=P(X_{k-1}).
\end{align*}
Since $k$ was arbitrary, we may apply this result to $k-1,$ and so on to say that $P(X_{k})=\frac{x}{x+y}$ for all $k\geq 1.$
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

With $\ds{\quad X \equiv x/m\quad\mbox{and}\quad Y \equiv y/m}$:

\begin{align}
&\bbox[10px,#ffd]{\ds{%
\sum_{i=0}^{k}{k\choose i}{\prod_{j = 0}^{i - 1}\pars{x + jm}
\prod_{j = 0}^{k - i - 1}\pars{y + jm} \over
\prod_{j = 0}^{k - 1}\pars{x + y + jm}}}}
\\[5mm] = &\
\sum_{i = 0}^{k}{k\choose i}
{\bracks{m^{i}\prod_{j = 0}^{i - 1}\pars{j + x/m}}
\bracks{m^{k - i}\prod_{j = 0}^{k - i - 1}\pars{j + y/m}} \over
m^{k}\prod_{j = 0}^{k - 1}\bracks{j + \pars{x + y}/m}}
=
\sum_{i = 0}^{k}{k\choose i}{X^{\large\overline{\,i\,}}
Y^{\large\overline{k - i}} \over \pars{X + Y}^{\large\overline{k}}}
\\[5mm] = &\
\sum_{i = 0}^{k}{k\choose i}{\bracks{\Gamma\pars{X + i}/\Gamma\pars{X}}
\bracks{\Gamma\pars{Y + k - i}/\Gamma\pars{Y}}
\over \Gamma\pars{X + Y + k}/\Gamma\pars{X + Y}}
\\[5mm] = &\
{\Gamma\pars{X + Y} \over \Gamma\pars{X}\Gamma\pars{Y}}
\sum_{i = 0}^{k}{k\choose i}\
\overbrace{{\Gamma\pars{X + i}\Gamma\pars{Y + k - i}
\over \Gamma\pars{X + Y + k}}}^{\ds{\mrm{B}\pars{X + i,Y + k - i}}}\qquad
\pars{~\mrm{B}:\ Beta\ Function~}
\\[5mm] = &
{\Gamma\pars{X + Y} \over \Gamma\pars{X}\Gamma\pars{Y}}
\sum_{i = 0}^{k}{k \choose i}
\int_{0}^{1}t^{X + i - 1}\pars{1 - t}^{Y + k - i - 1}\,\dd t
\\[5mm] = &\
{\Gamma\pars{X + Y} \over \Gamma\pars{X}\Gamma\pars{Y}}
\int_{0}^{1}t^{X - 1}\pars{1 - t}^{Y + k - 1}
\sum_{i = 0}^{k}{k \choose i}\pars{t \over 1 - t}^{i}\,\dd t
\\[5mm] = &\
{\Gamma\pars{X + Y} \over \Gamma\pars{X}\Gamma\pars{Y}}
\int_{0}^{1}t^{X - 1}\pars{1 - t}^{Y + k - 1}
\pars{1 + {t \over 1 - t}}^{k}\,\dd t
\\[5mm] = &\
{\Gamma\pars{X + Y} \over \Gamma\pars{X}\Gamma\pars{Y}}\
\underbrace{\int_{0}^{1}t^{X - 1}\pars{1 - t}^{Y - 1}\,\dd t}
_{\ds{\mrm{B}\pars{X,Y}}}\ =\
{\Gamma\pars{X + Y} \over \Gamma\pars{X}\Gamma\pars{Y}}\
\bracks{\Gamma\pars{X}\Gamma\pars{Y} \over \Gamma\pars{X + Y}} = \bbx{\large 1}
\end{align}
A: You start off good:
$\operatorname{P}(X_1)=\frac{x}{x+y}$
$\operatorname{P}(Y_1)=\frac{y}{x+y}$
$\operatorname{P}(X_2)=\operatorname{P}(X_1)\operatorname{P}(X_2|X_1)+\operatorname{P}(Y_1)\operatorname{P}(X_2|Y_1)=\frac{x}{x+y}\frac{x+m}{x+m+y}+\frac{y}{x+y}\frac{x}{x+y+m}$
But you can simplify here:
$$\frac{x}{x+y}\frac{x+m}{x+m+y}+\frac{y}{x+y}\frac{x}{x+y+m} = $$
$$\frac{1}{x+y}\left(x\cdot\frac{x+m}{x+y+m}+y\cdot\frac{x}{x+y+m} \right)= $$
$$\frac{1}{x+y}\left(x\cdot\frac{x+m}{x+y+m}+x\cdot\frac{y}{x+y+m} \right) =$$
$$\frac{x}{x+y}\left(\frac{x+y+m}{x+y+m}\right) = $$
$$\frac{x}{x+y}$$
And thus by induction, $X_1 = X_k$.
