<s>[INST] Prove that for $n\ge 2$, $2{n \choose 2}+{n \choose 1} = n^2$ Problem : Prove that for $n\ge 2$, $2{n \choose 2}+{n \choose 1} = n^2$
My Approach : I would assume that we can prove by induction.
Base case $n=2$.
$$=2{2 \choose 2}+ {2 \choose 1}= (2\cdot 1)+2 =4$$
$$n^2 =2^2 = 4.$$
Assume for $n\ge 2$, $n\ge 2$, $2{n \choose 2}+{n \choose 1} = n^2$  for $n \le k$.
Let $n=k+1$
$$2{k+1 \choose 2}+{k+1 \choose 1} = (k+1)^2$$
And, that's as far as I got.
I get stuck with the ${k+1 \choose 2}$ part.
 [/INST] We can also give this a combinatorial interpretation:


*

*$\binom{n}{2}$ is the number of unordered pairs of distinct elements of $\underline{n}$

*So $2\binom{n}{2}$ is the number of ordered pairs of distinct elements of $\underline{n}$

*So $2\binom{n}{2}+\binom{n}{1}$ is the number of ordered pairs of $\underline{n}$

*So $2\binom{n}{2}+\binom{n}{1}=|\underline{n}^2|$

*So $2\binom{n}{2}+\binom{n}{1}=n^2$
With enough care, this can be made into a rigorous proof (these are called "combinatorial proofs").
</s>