Limit on table size - perfect hashing
Ok, I managed to prove it:

We note that the total size of the tables = $$n^2 + \sum_i n_i^4$$
where $n^2$ is the first table and $n_i$ is the size of the $i$th index of table with collisions. 
Therefore we get:

$$n^2 + \sum_i n_i^4 = n^2 +\sum_i (n_i^2)^2 \le n^2 + \sum_i (4\binom{n_i}{2})^2 \le n^2 + 16(\sum_i \binom{n_i}{2}) = n^2 +16(\text{number of collisions})^2 = n^2 + 16n^2 = O(n^2)$$