Prove that $\binom n2 + \binom {n-1}2$ is always a perfect square

Question

Prove that if $n$ is a positive integer and $n >1$: $$\binom n2 + \binom {n-1}2$$ is always a perfect square.

I know we need to turn that into a binomial, but I can't follow how. Please note I'm pretty new to discrete math. Thanks in advance.

Answer 1

HINT: $$\binom{n}2=\frac{n!}{2!(n-2)!}=\frac{n(n-1)}2\;.$$ Apply the same idea to $\binom{n-1}2$, add the resulting fractions, and simplify.

Alternatively, if you know that $1+2+\ldots+n=\frac{n(n+1)}2=\binom{n+1}2$, you can observe that

$$\color{green}{\binom{n}2=1+2+\ldots+(n-2)+(n-1)}\;,$$

and

$$\color{brown}{\binom{n-1}2=1+2+\ldots+(n-3)+(n-2)}\;.$$

Now look at the picture below:

$$\begin{array}{ccc} &1&2&3&\ldots&n-3&n-2&n-1\\ 1&\color{green}\bullet&\color{brown}\bullet&\color{brown}\bullet&\ldots&\color{brown}\bullet&\color{brown}\bullet&\color{brown}\bullet\\ 2&\color{green}\bullet&\color{green}\bullet&\color{brown}\bullet&\ldots&\color{brown}\bullet&\color{brown}\bullet&\color{brown}\bullet\\ 3&\color{green}\bullet&\color{green}\bullet&\color{green}\bullet&\ldots&\color{brown}\bullet&\color{brown}\bullet&\color{brown}\bullet\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ n-3&\color{green}\bullet&\color{green}\bullet&\color{green}\bullet&\ldots&\color{green}\bullet&\color{brown}\bullet&\color{brown}\bullet\\ n-2&\color{green}\bullet&\color{green}\bullet&\color{green}\bullet&\ldots&\color{green}\bullet&\color{green}\bullet&\color{brown}\bullet\\ n-1&\color{green}\bullet&\color{green}\bullet&\color{green}\bullet&\ldots&\color{green}\bullet&\color{green}\bullet&\color{green}\bullet\\ \end{array}$$

Answer 2

$$\binom{n}{2} + \binom{n-1}{2} = \frac{n!}{(n-2)!2!}+\frac{(n-1)!}{(n-1-2)!2!} = \frac{n(n-1)}{2}+\frac{(n-1)(n-2)}{2}.$$

Can you take it from here?

Answer 3

Besides the beautiful approach in Brian M. Scott's answer, there is another combinatorial way to do it by using Pascal's recursion(i.e. $\binom{n-1}{k-1}+\binom{n-1}{k}=\binom{n}{k}$).
$\binom{n-1}{2}+\binom{n}{2}=\binom{n-1}{2}+\binom{n-1}{2}+\binom{n-1}{1}=2\binom{n-1}{2}+\binom{n-1}{1}=2\binom{n-1}{2}+(n-1)$.
Suppose you have two elements to be colored and you have $n-1$ colors (you can do it in $(n-1)*(n-1)$ ways why?). There are 2 disjoint cases, you color the two object with the same color in $n-1$ ways, or you can color the two object with different colors, you can choose the two colors in $\binom{n-1}{2}$ ways and to permute the chosen colors you have just 2 ways. Using multiplicative principle and addition principle, you would have that $(n-1)^2=2\binom{n-1}{2}+(n-1)$.

Answer 4

Let us see how many pairs $(a,b)$ can be formed using $n-1$ elements.

Straightforward way: $(n-1)^2$.

Round about way: We have ${n-1}\choose 2$ pairs $(a,b)$, where $(a,b)$ and $(b,a)$ are counted the same (so we need to double the count), and $(a,a)$ (which are $n-1$ in number) is not accounted for. So, Taking care of this undercounting, we have $$ 2{{n-1}\choose 2} + {{n-1}\choose 1} = {{n-1}\choose 2} + \underbrace{{{n-1}\choose 2} + {{n-1}\choose 1}}_{{n\choose 2}} = {{n-1}\choose 2} + {{n-1}\choose 1} $$ So, $(n-1)^2$ equals ${{n-1}\choose 2} + {{n-1}\choose 1}$.

Answer 5

Another combinatorial answer

Suppose I have two urns. One has the numbers $1$ through $n-1$ in it and the other has those plus a red ball with no number. Consider the following way to select from the urns. First choose an urn. If you choose the urn with the red ball, then take two balls. If the one of the balls is the red ball and the other is $a$, then call your selection $(a,a)$. Otherwise, order the balls in increasing order. If you draw from the other urn, you must get two different numbers, so order them in decreasing order. Thus there $\binom n2 + \binom {n-1}{2}$ ways to draw balls. Furthermore, the possible selections are exactly the ordered pairs $(a,b)$ with $a,b$ between $1$ and $n-1$, possibly with a repeat, so there are $(n-1)^2$ of them.

Answer 6

A small contribution, in addition to the excellent answers already posted above. $$\begin{align} \binom n2 + \binom {n-1}2 &=\binom n2 + \frac{n-2}{n}\binom n2\\ &=\left(1+\frac{n-2}n\right)\binom n2\\ &=\frac{2(n-1)}n \cdot\frac{n(n-1)}2\\ &=(n-1)^2\qquad \blacksquare \end{align}$$