$2.(15$pts$)$ The worst$-$case running time for quicksort is given by the recurrence T$($n$)=$ T$($n$-1)+($n$).$ Use the substitution method to prove that this recurrence has the solution T$($n$)=($n$2),$ as claimed at the beginning of section $7\mathrm{.}2.$