[proofplan] Suppose $L$ is a nonempty regular language with pumping number $n$; we must exhibit some $w \in L$ with $|w| < n$. Pick any $w \in L$. If $|w| < n$ we are done, so assume $|w| \geq n$. We apply the pumping lemma to extract a decomposition $w = xyz$ with $|y| \geq 1$ and $|xy| \leq n$ such that $xy^k z \in L$ for every $k \geq 0$. Setting $k = 0$ ("pumping down") deletes the loop and produces $xz \in L$ with $|xz| = |w| - |y| < |w|$. Iterating the construction gives a strictly decreasing sequence of word lengths in $L$, all non-negative integers, so after finitely many steps the length drops below $n$. We make this precise by strong induction on $|w|$. [/proofplan] [step:Fix the data and set up strong induction on word length] Since $L$ is a nonempty regular language, we may fix some element $w_0 \in L$. Let $n$ be a pumping number for $L$: that is, for every $w \in L$ with $|w| \geq n$, there exists a decomposition \begin{align*} w &= xyz, & |y| &\geq 1, & |xy| &\leq n, & xy^k z &\in L \text{ for all } k \geq 0, \end{align*} as supplied by the [Pumping Lemma for Regular Languages](/theorems/1793). We prove the following statement by strong induction on $m$: $P(m)$: for every regular language $L'$ with pumping number $n$, if $L'$ contains a word of length $m$, then $L'$ contains a word of length strictly less than $n$. Applying $P(|w_0|)$ to $L' := L$ and the witness $w_0 \in L$ yields the desired conclusion. We fix $L$ and $n$ throughout and prove $P(m)$ for all $m \in \mathbb{N}_0 := \{0, 1, 2, \dots\}$. [/step] [step:Handle the base cases $m < n$ directly] Suppose $m < n$ and $L$ contains a word of length $m$. That word itself has length $m < n$, so $L$ contains a word of length strictly less than $n$. Hence $P(m)$ holds whenever $m < n$. In particular the cases $m = 0, 1, \dots, n - 1$ of $P(m)$ are immediate. [/step] [step:Apply the pumping lemma to pump down and obtain a strictly shorter word in $L$] Fix $m \geq n$ and assume as the strong inductive hypothesis that $P(m')$ holds for every $m' \in \{0, 1, \dots, m - 1\}$. Suppose $w \in L$ has $|w| = m$. Since $|w| = m \geq n$, the pumping lemma applies to $w$: there exist words $x, y, z \in \Sigma^\star$ with \begin{align*} w &= xyz, & |y| &\geq 1, & |xy| &\leq n, & xy^k z &\in L \text{ for all } k \geq 0. \end{align*} Specialising to $k = 0$ gives \begin{align*} xy^0 z &= xz \in L. \end{align*} (We use the convention that $y^0 = \varepsilon$, so $xy^0 z = x \varepsilon z = xz$.) Compute the length of $xz$: \begin{align*} |xz| &= |x| + |z| = (|x| + |y| + |z|) - |y| = |w| - |y| = m - |y|. \end{align*} Since $|y| \geq 1$, \begin{align*} |xz| &= m - |y| \leq m - 1 < m. \end{align*} In particular $|xz| \in \{0, 1, \dots, m - 1\}$. [/step] [step:Close the strong induction] Set $m' := |xz|$. Then $m' \leq m - 1$, so by the strong inductive hypothesis $P(m')$ holds: since $L$ contains the word $xz$ of length $m'$, $L$ contains a word of length strictly less than $n$. This establishes $P(m)$. By the principle of strong induction on $m \in \mathbb{N}_0$, $P(m)$ holds for every $m \in \mathbb{N}_0$. [guided] The strong inductive skeleton packages the intuitive "keep pumping down until the word is shorter than $n$" argument into a formal proof by induction on word length. Why strong induction and not weak induction? The pumping lemma guarantees a decrease, but not necessarily a decrease by exactly one. If $w$ has length $m \geq n$ and the pump $y$ has length $|y| = \ell \geq 1$, then $xz$ has length $m - \ell$. This new length could be anywhere in $\{m - n, m - n + 1, \dots, m - 1\}$ — we only control $|y| \geq 1$ and $|xy| \leq n$, which give $1 \leq |y| \leq n$. So the shortened word's length is some element of $\{0, 1, \dots, m - 1\}$, but we cannot pin it down more precisely. Strong induction handles this: $P(m)$ depends on $P(m')$ for *any* $m' < m$, not just $m' = m - 1$. The base cases are the indices $m < n$. For these $m$, $P(m)$ is automatic: a word of length $m < n$ is already a witness to the conclusion. No pumping happens at this level — the "short" words are the ones we are trying to produce, and the induction exits through them. One might worry: could the pumping process cycle indefinitely, or somehow fail to reach a word of length $< n$? It cannot, because each pump-down step strictly decreases word length in $\mathbb{N}_0$, and $\mathbb{N}_0$ is well-ordered. Any strictly decreasing sequence in $\mathbb{N}_0$ is finite. The strong induction makes this termination argument precise: the induction proceeds on the well-founded order $<$ on $\mathbb{N}_0$. A concrete trace makes the argument tangible. Suppose $n = 3$ and $w = aaaaaaa \in L$ (length $7$). The pumping lemma hands us $w = xyz$ with $|y| \geq 1$, $|xy| \leq 3$; perhaps $x = \varepsilon$, $y = aa$, $z = aaaaa$. Pumping down: $xz = aaaaa$ (length $5$). That is still $\geq n$, so we pump again. Perhaps this time $y' = a$ and $xz$ becomes $aaaa$ (length $4$), then $aaa$ (length $3$, still $\geq n$), then $aa$ (length $2 < n$) — and we stop. The sequence of word lengths $7, 5, 4, 3, 2$ is strictly decreasing in $\mathbb{N}_0$; the induction captures exactly this. [/guided] [/step] [step:Apply the principle to the initial witness] Since $L$ is nonempty, pick any $w_0 \in L$, and set $m_0 := |w_0| \in \mathbb{N}_0$. Applying $P(m_0)$ to the witness $w_0$: $L$ contains a word of length strictly less than $n$. Call any such word $w$; then $w \in L$ and $|w| < n$, which is exactly the conclusion of the theorem. This completes the proof. [/step]