Proof the ideal soliton distribution is a probability mass function


The ideal soliton distribution arises in LT codes. For positive integer values $N$ and $k \in [2,N]$ it is given by $$p(1)=\frac{1}{N}$$ $$p(k)=\frac{1}{k(k-1)}$$ It is zero otherwise. In order to be a probability mass function $\sum_i p(i)$ must be 1 for any $N$.


By induction. The statement holds for $N=1,2$. Assume the statement holds for a given $N$. We have $$\frac{1}{N} + \sum_{i=2}^N\frac{1}{i(i-1)} = 1$$ Then $$\sum_{i=2}^N \frac{1}{i(i-1)} = \frac{N-1}{N}$$ Add $1/(N+1)N$ to both sides. This would be the next term in the summation. $$\sum_{i=2}^N \frac{1}{i(i-1)} + \frac{1}{(N+1)N} = \frac{N-1}{N} + \frac{1}{(N+1)N}$$ Simplify the left hand side $$\sum_{i=2}^N \frac{1}{i(i-1)} + \frac{1}{(N+1)N} = \sum_{i=2}^{N+1} \frac{1}{i(i-1)}$$ And the right hand side $$\frac{N-1}{N} + \frac{1}{(N+1)N} = \frac{N}{N+1}$$ Giving $$\sum_{i=2}^{N+1} \frac{1}{i(i-1)} = \frac{N}{N+1}$$ Add $1/(N+1)$ to both sides to get the final result $$\frac{1}{N+1} + \sum_{i=2}^{N+1} \frac{1}{i(i-1)} = 1$$ The statement holds for $N+1$ as desired.