Trying to understand this Quicksort Correctness proof
We are indeed assuming $P(k)$ holds for all $k &lt; n$. This is a generalization of the "From $P(n-1)$, we prove $P(n)$" style of proof you're familiar with.

The proof you describe is known as the principle of strong mathematical induction and has the form


  Suppose that $P(n)$ is a predicate defined on $n\in \{1, 2, \dotsc\}$. If we can show that
  
  
  $P(1)$ is true, and
  $(\forall k &lt; n \;[P(k)])\Longrightarrow P(n)$
  
  
  Then $P(n)$ is true for all integers $n\ge 1$.


In the proof to which you refer, that's exactly what's going on. To use quicksort to sort an array of size $n$, we partition it into three pieces: the first $k$ subarray, the pivot (which will be in its correct place), and the remaining subarray of size $n-k-1$. By the way partition works, every element in the first subarray will be less than or equal to the pivot and every element in the other subarray will be greater than or equal to the pivot, so when we recursively sort the first and last subarrays, we will wind up having sorted the entire array.

We show this is correct by strong induction: since the first subarray has $k&lt;n$ elements, we can assume by induction that it will be correctly sorted. Since the second subarray has $n-k-1&lt;n$ elements, we can assume that it will be correctly sorted. Thus, putting all the pieces together, we will wind up having sorted the array.