Prove $\sum_{i=1}^{m}A_{i} = n\left(1 - 1(1-\frac1n)^m\right)$, where $A_{m}= 1-\frac{A_{m-1}+A_{m-2}+\ldots+A_{2}+A_{1}}{n}$ and $A_1=1$

Question

Prove $\sum_{i=1}^{m}A_{i} = n\left(1 - 1(1-\frac1n)^m\right)$, where $A_{m}=1-\frac{A_{m-1}+A_{m-2}+\ldots+A_{2}+A_{1}}{n}$ and $A_1=1$ for $m,n>0$.

I don't have any idea on how to simplify these.

The question that inspired this is the expected number of distinct values if we draw $m$ times from $[1,n]$. RHS and LHS were two approaches that I used to solve the problem, and were proven computationally to be equivalent.

Answer 1

Define: $S_m=A_1+...+A_m$, so we have:

$$A_m=S_m-S_{m-1}=1-\frac{1}n S_{m-1}$$

$$S_m=\beta S_{m-1}+1,~~~~\beta=\left(1-\frac{1}n\right),~~~~S_1=A_1=1$$

$$S_m+\frac{1}{\beta-1}=\beta\left(S_{m-1}+\frac{1}{\beta-1}\right)$$

Let $C_m=S_{m}+\frac{1}{\beta-1}$, $C_1=1+\frac{1}{\beta-1}=1-n,$

$$\frac{C_m}{C_{m-1}}=\beta$$

Can you proceed from here?

Answer 2

Since you already have an expression for $\sum_{i=1}^m A_i$, we can prove it's correct by induction on $m$.

---

First, the base case. When $m=1$, we have $$\sum_{i=1}^m A_i = A_1 = 1$$ and $$n(1-(1-\tfrac1n)^m) = n(1-(1-\tfrac1n)) = 1.$$ Therefore $$\sum_{i=1}^m A_i = n(1-(1-\tfrac1n)^m)$$ holds when $m=1$.

---

For the inductive step, suppose $$\sum_{i=1}^kA_i = n(1-(1-\tfrac1n)^k)$$ is true for some $k \geq 1$. Then $$\begin{align*} \sum_{i=1}^{k+1} A_i &= A_{k+1} + \sum_{i=1}^k A_i \\ &= \left(1 - \frac{\sum_{i=1}^k A_i}{n}\right) + \sum_{i=1}^k A_i \\ &= \left(1 - \frac{n(1-(1-\tfrac1n)^k)}{n}\right) + \left(n(1-(1-\tfrac1n)^k)\right) \\ &= (1-\tfrac1n)^k + n(1-(1-\tfrac1n)^k) \\ &= n\left(\tfrac1n(1-\tfrac1n)^k + 1 - (1-\tfrac1n)^k\right) \\ &= n\left(1 - (1-\tfrac1n)(1-\tfrac1n)^k\right) \\ &= n\left(1 - (1-\tfrac1n)^{k+1}\right) \end{align*}$$ which finishes the inductive step.