In Algorithms (4th ed.) by Robert Sedgewick and Kevin Wayne at page 199 it's illustrated how the cost of resizing a stack (based on a dynamic array) is amortized among the most recent push operations:
Proposition E. In the resizing array implementation of Stack (Algorithm 1.1), the average number of array accesses for any sequence of push and pop operations starting from an empty data structure is constant in the worst case.
Proof sketch: For each push operation that causes the array to grow (say from size N to size 2N), consider the n/2 - 1 push operations that most recently caused the stack size to grow to k, for k from n/2 + 2 to N. Averaging the 4N array accesses to grow the array to size 2N (2N array accesses to copy the N items and 2N array accesses to initialize an array) with n/2 - 1 array accesses (one for each push), we get an average cost of 9 array accesses for each of these n/2 - 1 push operations. Establishing this proposition for any sequence of push and pop operations is more intricate (see Exercise 1.4.32)
I cannot do the math to get the 9 result stated in the proof sketch:
$\require{cancel}$
$$\frac{4n+n/2-1}{n/2-1} = \frac{8n+n-2}{1\cancel2} \times \frac{1\cancel2}{n-2} = \frac{9n-2}{n-2} = ???$$
Can anybody show me the right way to get this result? Did I misunderstand the proof?
Consider $n / 2 - 1$ push operations that most recently caused the stack size to grow together with the last operation which causes the array to grow. Then you get one more operation both in numerator and denominator, thus the fractions equal to $9$.