<s>[INST] How to show that this difference of products is $O \left( \frac{1}{n^2} \right) $ Let $k \leq n$. Consider the following difference of products:
$$ \prod_{i=1}^{k-1} \left( 1 - \frac{i}{n+1} \right) - \prod_{i=1}^{k-1} \left( 1 - \frac{i}{n} \right)$$
For $n=1,2,3$, this is clearly $O \left( \frac{1}{n^2} \right) $ for $k=1,2,3$ respectively. How to show it for arbitrary $n$? And is it possible to give an estimate $C$ such that the difference is less than $\frac{C}{n^2}$?
 [/INST] $$\begin{align}\prod_{i=1}^{k-1}{\left (1-\frac{i}{n+1} \right )} &= \prod_{i=1}^{k-1}{\left (1-\frac{i}{n} + \frac{i}{n^2} \right )} + O \left (\frac1{n^3} \right )\\ &= \prod_{i=1}^{k-1}{\left (1-\frac{i}{n}  \right )} + \sum_{j=1}^{k-1}\frac{j}{n^2} \prod_{i=1,i \ne j}^{k-1}{\left (1-\frac{i}{n}  \right )}+ O \left (\frac1{n^3} \right )\\ &=\prod_{i=1}^{k-1}{\left (1-\frac{i}{n}  \right )} + \sum_{j=1}^{k-1}\frac{j}{n^2}+O \left (\frac1{n^3} \right )\\ &=\prod_{i=1}^{k-1}{\left (1-\frac{i}{n}  \right )} + \frac{k(k-1)}{2 n^2}+O \left (\frac1{n^3} \right )\end{align}$$
Thus the difference is, when $k \lt n$,
$$\frac{k(k-1)}{2 n^2}+O \left (\frac1{n^3} \right )$$
</s>