0
$\begingroup$

I came across the following proof in my textbook that was used as a end of chapter review. How can I prove the following algebraically?

$$\left( \begin{array}{c} 2n \\ n\ \end{array} \right) = 2 \left( \begin{array}{c} n \\ 2\ \end{array} \right) + n^2$$

$\endgroup$

closed as off-topic by Andrés E. Caicedo, Did, Hans Engler, hardmath, caverac Feb 2 '18 at 19:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Did, Hans Engler, hardmath, caverac
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    $\begingroup$ Is there a typo? I don't think that's true $\endgroup$ – John Doe Feb 2 '18 at 15:25
  • $\begingroup$ n=1 is false?! Isn't it? $\endgroup$ – Ivan Di Liberti Feb 2 '18 at 15:28
  • 2
    $\begingroup$ Left hand side should be $\left( \begin{array}{c} 2n \\ 2\ \end{array} \right)$ I think. $\endgroup$ – Marc Paul Feb 2 '18 at 15:29
  • $\begingroup$ FWIW, $\binom{2n}{n}\geq \frac{4^{n}}{2n+1},$ so if that is what the book said, it is way off base because the left side increases exponentially, while the right side does not. $\endgroup$ – Thomas Andrews Feb 2 '18 at 15:38
  • $\begingroup$ yes sorry that was a typo! $\endgroup$ – user104 Feb 2 '18 at 16:19
3
$\begingroup$

As an alternative, with the typo correction we have

$$\begin{eqnarray*} \binom{2n}{2} = 2 \binom{n}{2}+n^2 \end{eqnarray*}$$

which can be interpreted in this way

  • LHS is the number of couples we can choose among $2n$
  • RHS is the same choice mabe by dividing in two groups of n; indeed we can choose $\binom{n}{2}$ couples from the first group + $\binom{n}{2}$ couples from the second group and then the couples made of 1 from the first group and 1 from the second that is $n\cdot n=n^2$
$\endgroup$
  • $\begingroup$ is this a complete proof? $\endgroup$ – user104 Feb 2 '18 at 16:20
  • $\begingroup$ would this be considered a algebraic proof or combinatorial? $\endgroup$ – user104 Feb 2 '18 at 16:22
  • 1
    $\begingroup$ It is combinatorial of course, I’ve given it as an interesting alternative $\endgroup$ – gimusi Feb 2 '18 at 16:30
  • $\begingroup$ okay this makes sense as a complete combinatorial proof, thanks! $\endgroup$ – user104 Feb 2 '18 at 16:36
  • $\begingroup$ Maybe of interest:math.stackexchange.com/questions/2533960/… $\endgroup$ – Peter Szilas Feb 2 '18 at 16:45
6
$\begingroup$

Typo alert \begin{eqnarray*} \binom{2n}{\color{red}{2}} = 2 \binom{n}{2}+n^2. \end{eqnarray*}

Now use $\binom{n}{2} =\frac{n(n-1)}{2}$ and the above formula is easy to prove.

$\endgroup$
  • $\begingroup$ thanks that was a typo, could you show me how to use that formula? I haven't seen it before $\endgroup$ – user104 Feb 2 '18 at 16:20
  • $\begingroup$ would this be considered a algebraic proof or combinatorial? $\endgroup$ – user104 Feb 2 '18 at 16:22
  • $\begingroup$ Yes, this is an algebriac proof ... still trying to think of a nice combinatorial arguement that demonstrates the formula ... $\endgroup$ – Donald Splutterwit Feb 2 '18 at 16:32
  • $\begingroup$ how do I use that formula you gave? that would conclude the algebraic proof $\endgroup$ – user104 Feb 2 '18 at 16:36
  • $\begingroup$ \begin{eqnarray*} \binom{2n}{2} = \frac{ 2n(2n-1)}{2} = \cdots \end{eqnarray*} and now see DrSG's solution. $\endgroup$ – Donald Splutterwit Feb 2 '18 at 16:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.