Understanding a bound for derivation length of any string in Pumping lemma for context-free languages

Question

The following is a proof of the pumping lemma for context-free languages from Theorem 8.1 in "An Introduction to Formal Languages and Automata (6th ed.)" by Peter Linz:

Let $L$ be an infinite context-free language. Then there exists some positive integer $m$ such that any $w\in L$ with $|w|\ge m$ can be decomposed as

$$w=uvxyz,$$ with

$$|vxy|\le m,$$ and

$$|vy|\ge1,$$ such that

$$uv^ixy^iz\in L,$$ for all $i=0,1,2,\cdots$. This is known as the pumping lemma for context-free languages.

Proof: Consider the language $L−\{\lambda\}$, and assume that we have for it a grammar $G$ without unit-productions or $\lambda$-productions. Since the length of the string on the right side of any production is bounded, say by $k$, the length of the derivation of any $w\in L$ must be at least $|w|/k$. Therefore, since $L$ is infinite, there exist arbitrarily long derivations and corresponding derivation trees of arbitrary height.

...

I don't understand that "Since the length of the string on the right side of any production is bounded, say by $k$, the length of the derivation of any $w\in L$ must be at least $|w|/k$".

Specifically, where does the "$|w|/k$" come from?

Answer 1

Consider a word $x\in (V\cup \Sigma)^*$. Applying a derivation rule on $x$ to derive a word $x'\in (V\cup \Sigma)^*$ adds at most $k-1$ symbols, that is, $ |x'| \leq |x|+k-1$. Therefore, if $S=x_0, x_1, x_2, \ldots, x_t = w$ is a derivation sequence of $w$, then by an iterative application of what we've established above, we have that $$ |w|=|x_t| \leq |x_{t-1}| + k -1 \leq |x_{t-2}| + 2k -2 \leq \cdots \leq |x_{t-t}| + tk - t $$ $$= |S| + tk-t = tk -t + 1$$

and so $t\geq \frac{|w|-1}{k-1}$.