Prove the following summation of binomial coefficients. \[ \sum_{i=0}^n \sum_{j=0}^m {i+j \choose j} = {n + m +2 \choose n+1} – 1. \] First, by Pascal’s rule that \({i+j \choose j} = {i+j-1 \choose j} + {i+j-1 \choose j-1} \),…
Prove the following summation of binomial coefficients. \[ \sum_{i=0}^n \sum_{j=0}^m {i+j \choose j} = {n + m +2 \choose n+1} – 1. \] First, by Pascal’s rule that \({i+j \choose j} = {i+j-1 \choose j} + {i+j-1 \choose j-1} \),…
Consider the sum of a sequence of independent random variables. One may expect its distribution is concentrated around its expected value. This is characterized by the Chernoff bound, which gives exponentially decreasing bounds on tail distributions of the sum. Let…