Why is this sum zero? I have been looking at the following sum (for any positive integer $n$)
$$\left(1-\frac{1^2}{n}\right) + \left(1-\frac{1}{n}\right)\left(1-\frac{2^2}{n}\right) + \left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right)\left(1-\frac{3^2}{n}\right) + \ldots $$
Note that the $i$th term in the sum has $i$ factors and  is 
$$\left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right)\left(1-\frac{3}{n}\right)\dots \left(1-\frac{i-1}{n}\right)\left(1-\frac{i^2}{n}\right).$$  
It seems, amazingly, that the answer is 0. How can one show this?


The following holds true for $n\geq 1$
\begin{align*}
\sum_{k=1}^{\infty}\left(1-\frac{k^2}{n}\right)\prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right)=0\tag{1}
\end{align*}

Note, the empty product is set equal to $1$. We start by transforming the product into a somewhat more convenient form . 

\begin{align*}
\sum_{k=1}^{\infty}&\left(1-\frac{k^2}{n}\right)\prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right)\\
&=\sum_{k=1}^{n}\left(1-\frac{k^2}{n}\right)\frac{1}{n^{k-1}}\prod_{j=1}^{k-1}(n-j)\tag{2}\\
&=n!\sum_{k=1}^{n}\left(1-\frac{k^2}{n}\right)\frac{1}{n^k}\frac{1}{(n-k)!}\\
&=\frac{n!}{n^n}\sum_{k=0}^{n-1}\left(1-\frac{(n-k)^2}{n}\right)\frac{n^k}{k!}\tag{3}\\
\end{align*}

In (2) we set the upper limit of the sum to $n$ since for values greater than $n$ the product contains a factor zero. In the last step (3) we changed the index summation $k\rightarrow n-k$. In the following we skip the factor $\frac{n!}{n^n}$ and show the sum is equal to zero.

\begin{align*}
\sum_{k=0}&\left(1-\frac{(n-k)^2}{n}\right)\frac{n^k}{k!}\\
&=\frac{1}{n}\sum_{k=0}^{n-1}(n-n^2+2kn-k^2)\frac{n^k}{k!}\\
&=(1-n)\sum_{k=0}^{n-1}\frac{n^k}{k!}+2\sum_{k=1}^{n-1}k\frac{n^k}{k!}
-\frac{1}{n}\sum_{k=2}^{n-1}k(k-1)\frac{n^k}{k!}-\frac{1}{n}\sum_{k=1}^{n-1}k\frac{n^k}{k!}\tag{4}\\
&=(1-n)\sum_{k=0}^{n-1}\frac{n^k}{k!}+2n\sum_{k=0}^{n-2}\frac{n^k}{k!}
-n\sum_{k=0}^{n-3}\frac{n^k}{k!}-\sum_{k=0}^{n-2}\frac{n^k}{k!}\tag{5}\\
&=\frac{n^{n-1}}{(n-1)!}-n\frac{n^{n-1}}{(n-1)!}+n\frac{n^{n-2}}{(n-2)!}\\
&=\frac{n^{n-1}}{(n-1)!}\left(1-n+(n-1)\right)\\
&=0\\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box
\end{align*}

Comment:


*

*In (4) we set the lower bounds of the index accordingly and use $k^2=k(k-1)+k$ to be able to cancel out factors of the factorial conveniently.

*In (5) we adjust the index accordingly to obtain equal summands for telescoping in the next step.

Added 2015-08-13: A note to the elegant approach of @BarryCipra due to a comment of @hypergeometric.
Let $R$ be a positive integer less than $n$. We obtain from (1)
\begin{align*}
\sum_{k=1}^{\infty}&\left(1-\frac{k^2}{n}\right)\prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right)\\
&=\sum_{k=1}^{R}\left(1-\frac{k^2}{n}\right)\prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right)+
\sum_{k=R+1}^{\infty}\left(1-\frac{k^2}{n}\right)\prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right)\\
&=\prod_{r=1}^R\left(1-\frac{r}{n}\right)\left(\sum_{k=1}^{R}\left(1-\frac{k^2}{n}\right)\prod_{j=k}^R\left(1-\frac{j}{n}\right)^{-1}\right.\\
&\qquad\qquad\qquad\qquad+\left.\sum_{k=R+1}^{\infty}\left(1-\frac{k^2}{n}\right)\prod_{j=R+1}^{k-1}\left(1-\frac{j}{n}\right)\right)\tag{6}\\
&=\prod_{r=1}^R\left(1-\frac{r}{n}\right)\left(R+\sum_{k=R+1}^{\infty}\left(1-\frac{k^2}{n}\right)\prod_{j=R+1}^{k-1}\left(1-\frac{j}{n}\right)\right)\tag{7}
\end{align*}

Comment:


*

*Observe the last line of @BarryCipras representation corresponds to (7) with $R=3$.

*Since we know that (7) is valid, we proceed from (6) to (7) by claiming the validity of the identity
\begin{align*}
\sum_{k=1}^{R}\left(1-\frac{k^2}{n}\right)\prod_{j=k}^R\left(1-\frac{j}{n}\right)^{-1}=R\qquad\qquad 1\leq R < n
\end{align*}
This identity is a nice by-product.


*

*When setting $R\geq n$ in (7) we observe, that the leftmost product contains a factor zero. But we can't use this argument in this derivation, since we have to consider in (6) the factors $\left(1-\frac{j}{n}\right)^{-1}$ which are undefined in case $j=n$. 

