I was reading the proof of the induction for this question and didn't understand the step where they did $t! > (n^2)^{t-n^2} = n^tn^{t-n^2} > n^t$. How is $n^2$ even related to the problem and if so how is the inequality even true?
Problem and solution
First notice that $(2n^2)!>(n^2)^{n^2}$. This is because $$ (2n^2)! = 1\cdot 2\cdot \dots \cdot n^2 \cdot (n^2+1) \cdot \dots \cdot 2n^2, $$
and there are $n^2$ factors after the $(n^2+1)$ factor (including).
Now when $t>2n^2$ we have $$ t! = 1\cdot 2\cdot \dots \cdot n^2 \cdot (n^2+1) \cdot \dots \cdot 2n^2 \cdot \dots \cdot t, $$
and there are $(t-n^2)$ factors after the $(n^2+1)$ factor (including).
In effect $t! > (n^2)^{t-n^2}$.
