Using a combinatorial proof (counting the same thing in different ways), show that:
$$2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i$$
I was thinking of having some set $A$ where $|A| = n$, and then trying to find the size of the power set $|P(A\times A)|$. That will get the left hand side of the equation, but I'm having deriving the right hand side in the same way. Thanks for any help!
On
Partition $P(A\times A)$ into subsets determined by how many distinct elements appear as the first coordinate, and count the size of each subset. For instance, with $n=3$, the element $$\{(1,1),(1,2), (1,3)\}$$belongs to the $i=1$ partition because it only has $1$ as first coordinate, while $$\{(1,2), (2,2), (3,3)\}$$ belongs to $i=3$.
Translated into the world of $n\times n$ square grids filled with 0 and 1: Split into cases depending on how many columns have at least one 1 in them.
On
Using a combinatorial proof (counting the same thing in different ways), show that:To show: $$2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i$$
Depending on what is intended by the phrase combinatorial proof, an alternative approach is that by the binomial theorem:
$$2^{(n^2)} = \left(2^n\right)^n = \left[ ~1 + \left(2^n - 1\right) ~\right]^n $$
$$= \sum_{i=0}^n \binom{n}{i} \left[1^{(n-i)} \times (2^n-1)^i\right].$$
On
This is already stated as a side-note in @Arthur's answer. But for me this is a prime example of a combinatorial proof. We want to show \begin{align*} \color{blue}{2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i}\tag{1} \end{align*} by counting a number of configurations in two different ways.
We assume we have an $n\times n$ chessboard and $n^2$ grains of rice.
One way: We take up to $n^2$ grains of rice and put a grain of rice on a square of the chessboard or not. Since there are $n^2$ squares on this chessboard we have \begin{align*} \color{blue}{2^{\left(n^2\right)}} \end{align*} pairwise different configurations of a chessboard filled with zero up to $n^2$ grains of rice.
Another way: Let's say a chess board has $n$ rows and $n$ columns. We classify the chess board configurations according to the number of rows which contain at least one grain of rice. We observe
The number of rows with at least on grain of rice can be $0$ up to $n$.
There are $\binom{n}{i}$ ways to choose $i$ non-empty rows, $0\leq i\leq n$.
Each non-empty row can be filled in $\left(2^n-1\right)$ different ways. The minus one indicates the empty row, which is not to count.
Putting these three statements into a formula we get \begin{align*} \color{blue}{\sum_{i=0}^n\binom{n}{i}\left(2^n-1\right)^i} \end{align*} pairwise different configurations to fill a chessboard with zero up to $n^2$ grains of rice and the claim (1) follows.
Your idea is exactly the right one. Let $A=\{1,\ldots, n\}$. Then the cardinality of the power set of $A\times A$ is $2^{(n^2)}$.
Let $\pi:A\times A\to A$ be the first coordinate projection $\pi(a,b)=a$. For $S\subset A\times A$, we let $\pi(S)=\{\pi(x):x\in S\}$. For each $S\subset A\times A$ and $a\in \pi(S)$, we let $S_a=\{b\in A:(a,b)\in S\}$. Then each $S\subset A\times A$ can be uniquely decomposed as $$S=\bigcup_{a\in \pi(S)}\{(a,b):b\in S_a\}$$ We can construct each $S$ by first choosing an $i$, then choosing a set $T\subset A$ with $|T|=i$ (which will eventually be $\pi(S)$), and then for each $a\in T$, we choose a set to be $S_a$. Note that by definition, if $a\in \pi(S)$, then $S_a$ is non-empty (which is where the $-1$ comes from in $2^n-1$).
First choose $i$.
Then choose $T$ with $|T|=i$. There are $\binom{n}{i}$ ways to do this.
For each $a\in T$, choose an $S_a$. There are $2^n-1$ ways to do this for an individual $a$, and there are $i$ values of $a$ in $T$, so we get $(2^n-1)^i$, one factor of $2^n-1$ for each $a$. Summing over $i$ counts the power set of $A\times A$.