Ways to colour elements of matrix using two colours

Question

Let $A$ be a $n \times n$ matrix and suppose we want to colour elements of this matrix using black and white colours. Since each element can be either white or black, so total number of ways are $2^{n^{2}}$. Now, I want to prove using counting in two ways that $$2^{n^{2}} = \sum_{i=0}^{n}\binom{n}{i}(2^{n}-1)^{i}.$$ Since there are $n+1$ terms in the sum, my idea is to consider rows $R_{1},R_{2},\cdots,R_{n}$ and try to colour these rows separately to get the number $\binom{n}{i}(2^{n}-1)^{i}$ for $i^{th}$ row. But I am not able to figure out, how to do it. Is there any other way to solve this counting in two ways problem?

Answer 1

For the RHS, count according to the number $i$ of rows that contain at least one white element. There are $\binom{n}{i}$ choices of $i$ rows and $2^n-1$ ways to color each of them (anything but all black). The remaining $n-i$ rows are all black.