This problem comes from the page 2 of "Probability - 1" of A.N. Shiryaev, where the book talks about the cardinality of finite unordered sampling with replacement.
Consider an urn consisting of $M$ balls, label from $1$ to $M$. We want to draw $n$ balls one by one with replacement. The cardinality of ordered sample space is $M^{n}$. By an unordered sample, denoted by using the bracket $[a_{1},\dots, a_{n}]$, I mean something like $[1,2,3,4]=[3,4,2,1]$, i.e. the order does not matter. And the sample space is described as $$\Omega=\{\omega:\omega=[a_{1},\dots, a_{n}],a_{i}=1,\dots, M\}.$$
The book wants to prove that the cardinality, denoted by $N(\Omega)$, is $$N(\Omega)={n+M-1\choose n}.$$
I know this is the cardinality of a multiset, but this book does not go to this notion, and prove this identity using mathematical induction and I do not understand why its induction works.
The proof basically goes as follows. Denoted by $N(k,n)$ the cardinality of the following sample space $$\{\omega:\omega=[a_{1},\dots, a_{n}],a_{i}=1,\dots, k\}.$$ For any $k\leq M$, it is clear that $N(k,1)=k={k+1-1\choose 1}$.
Now, suppose that $N(k,n)={k+n-1\choose n}$ for all $k\leq M$. He proved that $N(M,n+1)={M+n\choose n+1}$. I don't have the problem with this induction step. Basically, for an unordered sample, we can rearrange $a_{1},\dots, a_{n+1}$ in a non-decreasing order, $a_{1}\leq a_{2}\leq\dots\leq a_{n+1}$. So, if $a_{1}=1$, then the cardinality of the sample space $N(M,n)$, if $a_{1}=2$, then it is $N(M-1,n)$, etc. Therefore, $$N(M,n+1)=N(M,n)+N(M-1,n)+\dots+N(1,n).$$ Since we know that $N(k,n)={k+n-1\choose n}$ for all $k\leq M$, we can calculate the right-hand side using Pascal's identity.
What I do not understand is that: why does this induction even work? He basically inducts on $n$, so shouldn't he fix the $M$, suppose that $N(M,n)={M+n-1\choose n}$ for some (or all) $n$, and then prove it for $n+1$?
If he suppose that $N(k,n)={k+n-1\choose n}$ for all $k\leq M$ and he proved $N(M,n+1)$, what does this induction lead to?
Thank you in advance!
Edit 1: Formal Proof
Yeah so finally, I found this note http://www.math.ualberta.ca/~isaac/math324/s12/induction.pdf, and it provides the principle of double induction. In fact, I believe that the statement in the note is about the principle of Strong double induction.
I will state it within the context of our problem. For each $M$ and $n$, we denote by $N(M,n)$ the cardinality of the following sample space $$\Omega(M,n):=\{\omega:\omega=[a_{1},\dots, a_{n}],a_{i}=1,\dots, M\}.$$ We want to prove that $N(M,n)={M+n-1\choose n}$ for all integers $M,n\geq 1$. By the statement in this note, we need to prove the following three things.
$N(1,1)=1$.
Fixing an integer $M_{0}\geq 1$, suppose that $N(M_{0},1)=M_{0}$, we need to show that $N(M_{0}+1,1)=M_{0}+1$.
Fixing an integer $n_{0}\geq 1$, suppose that $N(M,n_{0})={M+n_{0}-1\choose n_{0}}$ for all $M\geq 1$, we need to show that $N(M,n_{0}+1)={M+n_{0}\choose n_{0}}$ is true for all $M\geq 1$.
$N(1,1)=1$ is clearly true. Moreover, the second requirement, in our case, is automatically true, because it is easy to see that $N(M,1)=M$ for any $M$. We need to prove the requirement $3$. The proof goes as follows.
Since the sample is unordered, we can rearrange $a_{1},\dots, a_{n_{0}+1}$ in a non-decreasing order so that $$\Omega(M,n_{0}+1)=\{\omega:\omega=[a_{1},\dots, a_{n_{0}+1}], a_{1}\leq \dots\leq a_{n_{0}+1}, a_{i}=1,\dots, M\}$$ can be decomposed into a finite union of disjoint sets $$\Omega_{k}:=\{\omega:\omega=[a_{1},\dots, a_{n_{0}+1}], a_{1}=k, a_{1}\leq\dots\leq a_{n_{0}+1}, a_{i}=1,\dots, M\ \text{for}\ i\neq 1\},\ \ k=1,\dots, M.$$ Then, it is easy to see that $$N(\Omega_{k})=N(M-(k-1),n_{0})$$ and it follows from the induction hypothesis that \begin{align*} N(M,n_{0}+1)&=N(M,n_{0})+N(M-1,n_{0})+\dots+N(1,n_{0})\\ &={M+n_{0}-1\choose n_{0}}+{M+n_{0}-2\choose n_{0}}+\dots+{n_{0}\choose n_{0}}. \end{align*} By the Pascal's identity, for all $k=1,\dots, M$, we have $${M+n_{0}-k\choose n_{0}}+{M+n_{0}-k\choose n_{0}+1}={M+n_{0}-k+1\choose n_{0}+1}.$$ Hence, $N(M,n_{0}+1)$ can be written as an alternating sum: \begin{align*} N(M,n_{0}+1)&={M+n_{0}-1\choose n_{0}}+{M+n_{0}-2\choose n_{0}}+\dots+{n_{0}\choose n_{0}}\\ &={M+n_{0}\choose n_{0}+1}-{M+n_{0}-1\choose n_{0}+1}+{M+n_{0}-1\choose n_{0}+1}-{M+n_{0}-2\choose n_{0}+1}+\dots+{n_{0}+2\choose n_{0}+1}-{n_{0}+1\choose n_{0}+1}+{n_{0}+1\choose n_{0}+1}\\ &={M+n_{0}\choose n_{0}+1}. \end{align*}
Some Comments:
a) I believe that the induction statement provided by the note is correct, since my proof using it is extremely close to the proof in the book.
b) the only different is that I didn't do this by $k\leq M$, and then prove $N(M,n_{0}+1)$. I do think that supposing for $k\leq M$ is redundant.
The proof is essentially using a slightly stronger assumption in its induction step, but because $k$ and $M$ are playing very similar roles it winds up working just fine.
Notice that while everything says that the statements are true for $k \leq M$, the value of $M$ is actually arbitrary. If you wanted, you could make it a little more rigorous by applying strong induction on $M$:
Note that $N(M, 1)$ has the desired form for all $M$.
Note also that $N(1, n)$ has the desired form for all $n$.
Assume that $N(k, n)$ is true for all values of $n$ and for all $k \leq M$ for some arbitrary $M$.
Assume that $N(M + 1, n)$ is true for some arbitrary $n$.
Show that under these assumptions, $N(M + 1, n + 1)$ is true.
Conclude via induction on $n$ that $N(M + 1, n)$ is true for all $n$ and the chosen $M$.
Then conclude via induction on $M$ that $N(M, n)$ is true for all $M$ and $n$.