Prove by induction that the recurrence form of bubble sort is $\Omega(n^2)$
Assuming $T(1)=1$, you can show by induction that $T(n) = \frac{n(n-1)}{2} + 1$.

The base case is trivial since $T(1) = 1 = \frac{1 \cdot 0}{2} + 1$.

As for the inductive step, suppose that the claim holds up to $T(n)$.
$\begin{align*}
T(n+1) &amp;= T(n) + (n+1) - 1 =\frac{n(n-1)}{2} + 1 + n  \\
 &amp;= \frac{n^2 -n +2n}{2} + 1 = \frac{n^2 + n}{2} + 1 = \frac{n(n+1)}{2} + 1 \\
&amp;= \frac{(n+1)((n+1) - 1)}{2} + 1.
\end{align*}
$