2
$\begingroup$

Prove by induction: $$\sum_{i=1}^n \binom{i}{2}= {n+1 \choose 3}$$

I already know that: $$\sum_{i=1}^n \binom{i}{2} = {i+1 \choose 2+1}$$

And the LHS is now equal: $$\sum_{i=1}^n \binom{i}{2} + {i+1 \choose 2+1}$$

How do I continue to solve by induction?

$\endgroup$
  • 2
    $\begingroup$ Something is not right with what you "already know". The variable $i$ is the index of summation, and it has no meaning on the right side of the second equation. $\endgroup$ – hardmath Nov 21 '15 at 4:53
1
$\begingroup$

Suppose for a fixed $n$ that $\color{blue}{\sum_{i=1}^n \binom{i}{2}= {n+1 \choose 3}}$.

Consider $\sum_{i=1}^{n+1} \binom{i}{2}$. Then

$$\sum_{i=1}^{n+1} \binom{i}{2}= \binom{n+1}{2} + \color{blue}{\sum_{i=1}^n \binom{i}{2}} = \binom{n+1}{2} + \color{blue}{\binom{n+1}{3}}.$$

Is the right hand side equal to $\binom{(n+1)+1}{3}$? If it is, then we've proved that the claim holds for $n+1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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