Prove for $n\ge 2$, $2\binom{n}{2}+\binom{n}{1}=n^2$

Question

I found this example, and I was wondering how would you prove these kinds of problems?

I thought of proving using $\left(\binom{n-1}{k+1}\right)+\left(\binom{n-1}{k}\right)=\left(\binom{n}{k}\right)$ for pascal triangle

but then again I thought this would be proved by induction.

just overall confused

Answer 1

From the definition of binomial coefficients: $$ \binom{n}{2} = \frac{n(n-1)}2 $$ so $$ 2\binom{n}{2} = n^2-n. $$ Similarly: $$ \binom{n}{1} = n $$ Adding it up, you get what you need.

Answer 2

From a combinatorial point of view, we are counting the set of elements $\{(i,j)\mid 1\leq i,j\leq n\}$ in two ways.

The first way is directly - there are $n^2$ such pairs - $n$ values for $i$ and $n$ values for $j$.

The second way is to first count the number of elements on the diagonal $(i,i)$ wich is $\binom{n}{1}$, and then count the number of elements not on the diagonal. There are two elements off the diagonal for each pair $\{a,b\}\in\{1,2,3,\dots,n\}$ with $a\neq b$, so there are $2\binom{n}{2}$ pairs off the diagonal.

In general, if there are $p_k(m)$ ways to partition a set of $m$ objects into $k$ non-empty sets, then $$n^m = \sum_{k=1}^{m} p_k(m)k!\binom{n}{k}$$

In the case $m=2$, we have $p_1(2)=p_2(2)=1$.

Answer 3

Suppose you have $n$ different items in a bag. You draw one item, replace it in the bag, and then draw again. The number of different two-item samples you could make is $n^2$.

We could count these outcomes a different way. There are two kinds of samples: those where you draw the same item twice and those where you draw two different items.

• The number of ways to draw the same item twice is $\frac{n}{1}$ (just select any one of the $n$ items to draw twice).
• The number of ways to draw two different items where order matters is $2 \binom{n}{2}$. The binomial coefficient disregards order, so multiplying this value by $2$ accounts for the order in which the two items may have been drawn.

Adding the two bulleted items gives the total number of ways to draw two items with replacement, which we've already noted is also equal to $n^2$.