Let $A$ be an additive set with common ambient group $Z$. Then for any integer $n\geq 1$, we have $$|nA|\leq \binom{|A|+n-1}{n}|A|, \quad \quad (*)$$ where $nA:=\underbrace{A+\dots+A}_{n\ \text{times}}.$
Proof: We argue by induction on $|A|$. If $|A|=1$, then both sides of $(*)$ are equal to $1$. If $|A|>1$, then we can write $A=B\cup \{x\}$ where $B$ is a non-empty set with $|B|=|A|-1$. Then $$nA=\bigcup_{j=0}^n(jB+(n-j)\cdot x)$$ and hence by the induction hypothesis and Pascal's triangle identity $$|nA|\leq \sum \limits_{j=0}^n|jB|\leq \sum \limits_{j=0}^n\binom{|A|-1+j-1}{j}=\binom{|A|+n-1}{n}$$ as claimed. (We adopt the convention that $0B=\{0\}$.)
This is an excerpt from Tao-Vu book (see Lemma 2.1 (Trivial sum estimates) on page 54). I remember when I read this proof while ago I understood it very well back then. Today for some reason I opened this lemma again and one interesting question arose.
Question: We prove this lemma by induction on $|A|$, right? But how do we obtain the inequality $|jB|\leq \binom{|B|+j-1}{j}$? I do know that $|B|=|A|-1<|A|$ but when we prove by induction we fix that parameter $n$, where $n$ is the number of iterated sums of $A$, i.e. $nA$.
Can anyone explain that moment please? Am I missing something?
