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?

Solution 1:

This might get you started:

$$\begin{align} &\left(1-{1^2\over n}\right)+\left(1-{1\over n}\right)\left(1-{2^2\over n}\right)+\left(1-{1\over n}\right)\left(1-{2\over n}\right)\left(1-{3^2\over n}\right)+\cdots\\ &\quad=\left(1-{1\over n}\right)\left(1+\left(1-{2^2\over n}\right)+\left(1-{2\over n}\right)\left(1-{3^2\over n}\right)+\cdots \right)\\ &\quad=\left(1-{1\over n}\right)\left(\left(2-{2^2\over n}\right)+\left(1-{2\over n}\right)\left(1-{3^2\over n}\right)+\cdots \right)\\ &\quad=\left(1-{1\over n}\right)\left(1-{2\over n}\right)\left(2+\left(1-{3^2\over n}\right)+\left(1-{3\over n}\right)\left(1-{4^2\over n}\right)+\cdots \right)\\ &\quad=\left(1-{1\over n}\right)\left(1-{2\over n}\right)\left(\left(3-{3^2\over n}\right)+\left(1-{3\over n}\right)\left(1-{4^2\over n}\right)+\cdots \right)\\ &\quad=\left(1-{1\over n}\right)\left(1-{2\over n}\right)\left(1-{3\over n}\right)\left(3+\left(1-{4^2\over n}\right)+\left(1-{4\over n}\right)\left(1-{5^2\over n}\right)+\cdots \right)\\ \end{align}$$

Solution 2:

This becomes somewhat less mysterious once we recognize that every term after the $n$th term includes $\left(1-\frac{n}{n}\right)=0$.

Solution 3:

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$.