[proofplan]
We prove the iterated bound $|A_1 + A_2 + \cdots + A_k| \geq \sum_{i=1}^{k} |A_i| - k + 1$ by induction on $k$, applying the [Cauchy-Davenport Theorem](/theorems/2604) at each step. The partial sum set $S_j = A_1 + \cdots + A_j$ grows by at least $|A_{j+1}| - 1$ at each application, and the size condition $\sum |A_i| \leq p + k - 1$ ensures the Cauchy-Davenport bound does not saturate prematurely.
[/proofplan]
[step:Set up the induction and define partial sum sets]
Define $S_1 = A_1$ and, for $j = 1, \ldots, k-1$, define $S_{j+1} = S_j + A_{j+1}$. Then $S_k = A_1 + A_2 + \cdots + A_k$.
We prove by induction on $j$ that
\begin{align*}
|S_j| \geq \min\!\left(p,\, \sum_{i=1}^{j} |A_i| - j + 1\right)
\end{align*}
for each $j = 1, \ldots, k$.
**Base case ($j = 1$).** We have $|S_1| = |A_1| = |A_1| - 1 + 1$, and $|A_1| \leq p$ since $A_1 \subseteq \mathbb{Z}_p$, so the bound holds.
[/step]
[step:Inductive step: apply Cauchy-Davenport to $S_j + A_{j+1}$]
Assume the bound holds for $S_j$. We apply the [Cauchy-Davenport Theorem](/theorems/2604) to the pair $(S_j, A_{j+1})$:
\begin{align*}
|S_{j+1}| = |S_j + A_{j+1}| \geq \min(p,\, |S_j| + |A_{j+1}| - 1).
\end{align*}
We consider two cases.
**Case 1: $|S_j| = p$.** Then $S_j = \mathbb{Z}_p$, so $S_{j+1} = S_j + A_{j+1} = \mathbb{Z}_p$ and $|S_{j+1}| = p$. The bound $|S_{j+1}| \geq \min(p, \sum_{i=1}^{j+1} |A_i| - j)$ holds since $p$ is at least as large as any value the minimum can take.
**Case 2: $|S_j| < p$.** By the induction hypothesis, $|S_j| \geq \sum_{i=1}^{j} |A_i| - j + 1$. Substituting into the Cauchy-Davenport bound:
\begin{align*}
|S_{j+1}| &\geq \min\!\left(p,\, |S_j| + |A_{j+1}| - 1\right) \\
&\geq \min\!\left(p,\, \sum_{i=1}^{j} |A_i| - j + 1 + |A_{j+1}| - 1\right) \\
&= \min\!\left(p,\, \sum_{i=1}^{j+1} |A_i| - j\right).
\end{align*}
In both cases, $|S_{j+1}| \geq \min(p,\, \sum_{i=1}^{j+1} |A_i| - (j+1) + 1)$, completing the induction.
[guided]
The induction maintains the invariant $|S_j| \geq \min(p, \sum_{i=1}^{j} |A_i| - j + 1)$. At each step, Cauchy-Davenport adds at least $|A_{j+1}| - 1$ to the lower bound (until we saturate at $p$).
Why does the calculation work? If $|S_j| < p$, the induction hypothesis gives a numerical lower bound, and Cauchy-Davenport says
\begin{align*}
|S_{j+1}| \geq \min(p, |S_j| + |A_{j+1}| - 1).
\end{align*}
Since $|S_j| \geq \sum_{i=1}^{j} |A_i| - j + 1$ and this quantity is less than $p$, we substitute:
\begin{align*}
|S_j| + |A_{j+1}| - 1 \geq \left(\sum_{i=1}^{j} |A_i| - j + 1\right) + |A_{j+1}| - 1 = \sum_{i=1}^{j+1} |A_i| - j.
\end{align*}
The $\min$ with $p$ is harmless: if $\sum_{i=1}^{j+1} |A_i| - j \geq p$, the bound gives $|S_{j+1}| \geq p$, which combined with $|S_{j+1}| \leq p$ means $S_{j+1} = \mathbb{Z}_p$.
If $|S_j| = p$, then $S_j = \mathbb{Z}_p$ and adding any non-empty set to $\mathbb{Z}_p$ gives $\mathbb{Z}_p$ again, so $|S_{j+1}| = p$ and the bound is immediate.
[/guided]
[/step]
[step:Conclude for $j = k$ using the size hypothesis]
Setting $j = k$, we obtain
\begin{align*}
|A_1 + A_2 + \cdots + A_k| = |S_k| \geq \min\!\left(p,\, \sum_{i=1}^{k} |A_i| - k + 1\right).
\end{align*}
Since $\sum_{i=1}^{k} |A_i| \leq p + k - 1$ by hypothesis, we have $\sum_{i=1}^{k} |A_i| - k + 1 \leq p$, so the minimum equals $\sum_{i=1}^{k} |A_i| - k + 1$. Therefore
\begin{align*}
|A_1 + A_2 + \cdots + A_k| \geq \sum_{i=1}^{k} |A_i| - k + 1.
\end{align*}
[guided]
The hypothesis $\sum_{i=1}^{k} |A_i| \leq p + k - 1$ is precisely what ensures the minimum resolves to the algebraic expression $\sum |A_i| - k + 1$ rather than to $p$. Without this condition, the bound would still hold in the weaker form $|A_1 + \cdots + A_k| \geq \min(p, \sum |A_i| - k + 1)$, but the explicit lower bound $\sum |A_i| - k + 1$ would not be valid (since it could exceed $p$, the maximum possible size of a subset of $\mathbb{Z}_p$).
When $\sum |A_i| > p + k - 1$, we get $|A_1 + \cdots + A_k| \geq p$ from the $\min(p, \ldots)$ form, meaning the sum set is all of $\mathbb{Z}_p$. The two cases together — the explicit bound when $\sum |A_i| \leq p + k - 1$ and the saturation $A_1 + \cdots + A_k = \mathbb{Z}_p$ otherwise — cover all situations.
[/guided]
[/step]
