# Give a combinatorial proof for $n^2 = n(n-1)+n$

The question is in the title. I have no idea how to do this one. I was trying to rewrite $$n^2$$ as $$\binom {n}{1} \times \binom {n}{1}$$. I was going to say the story is, suppose there are $$n$$ boys and $$n$$ girls. How many ways there are to pick $$1$$ boy and $$1$$ girl, which is the LHS. But then I don't have any idea how to prove the RHS.

• I see it geometrical: are of square equals sum of areas of two rectangles $n\cdot (n-1)$ and $n\cdot 1$. Oct 18 at 23:50
• I note $n(n-1) = 2 \binom{n}{2}$. Oct 18 at 23:53
• @zkutch omg that's so clever! Oct 19 at 0:26

One idea: consider counting ordered pairs of integers $$(a, b)$$ in the range $$\{1, \ldots, n\}$$. Count the cases $$a = b$$ and $$a \neq b$$ separately.

If we have two people that need to choose from $$n$$ items (not necessarily distinct),

then there are $$n \cdot n = n^{2}$$ possibilities.

If we instead count the distinct possibilities first we subtract one for the second person's choice, which gives $$n(n-1)$$.

Note that since we have $$n$$ items, there are exactly $$n$$ possibilities where they do choose the same item.

These are independent choices with the union being the first counting method:

i.e. Distinct + Not distinct = Not necessarily distinct.

Hence we add them and get $$n^{2}=n(n-1)+n$$.

• thank you! I has this thought at first but I denied it for some reason. Oct 19 at 0:24