3
$\begingroup$

I'm currently stuck trying to prove that for all items in the sequence $\binom{n+1}{2}$, for all $n\geq 1$, that $\binom{n+1}{2}=\sum \limits _{i=0}^ni$.

My first assumption is to solve for my base case, which would be $1$, so I calculated that $\binom{n}{k}=\frac{n!}{k!(n-k)!}$, therefore $\binom{n+1}{2}=\frac{(n+1)!}{(2)!(n+1-2)!}=\frac{(n+1)!}{2(n+1-2)!}$.

When $n=1$, $\frac{(n+1)!}{2(n+1-2)!}=\frac{(1+1)!}{2(1+1-2)!}=\frac{2!}{2(2-2)!}= \frac{2}{2\cdot 0!}=\frac{2}{2\cdot 1}=1$, and $\sum \limits _{i=0}^ni$ when $n=1$ is $1$, so the base case is true.

So for the inductive hypothesis I state that $n=k$, and for the inductive step I then try to prove that since it's true for $k$, how it should be true for $k+1$.

First I substitute $n$ in the formula for $k+1$:

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

And for the other side of the equality, $\sum \limits _{i=0}^ni=\sum \limits _{i=0}^ki$, therefore $\sum \limits _{i=0}^{k+1}i$.

From this, $\frac{(k+2)!}{2k!}$ should equal $\sum \limits _{i=0}^{k+1}i$.

It's from this point I'm stumped on what to do next on how to actually prove this statement. Are there certain properties I'm supposed to employ to substitute some of the terms, am I just supposed to plug in the next value for $n+1$ as $k+1$? Because if I do that then:

$\frac{(2+2)!}{2(2!)}=\sum \limits _{i=0}^2i\rightarrow \frac{4!}{4}=2\rightarrow 6\neq 2$.

$\endgroup$
2
  • 1
    $\begingroup$ You can simplify a lot if you recognize that $\binom{n+1}{2} = \frac{(n+1)n}{2}$. $\endgroup$
    – angryavian
    May 17, 2022 at 23:30
  • 3
    $\begingroup$ The induction step should reduce to proving that $~\displaystyle \binom{n+1}{2} + (n+1) = \binom{n+2}{2}.~$ This is because $$\left[\sum_{i=1}^{n+1} i\right] - \left[\sum_{i=1}^{n} i\right] = (n+1).$$ $\endgroup$ May 17, 2022 at 23:33

1 Answer 1

3
$\begingroup$

$$\binom{k+2}{2} = \frac{(k+2)!}{2k!} = \frac{(k+2)(k+1)}{2} = \frac{(k+1)k}{2} + (k+1) = \binom{k+1}{2} + (k+1).$$ By induction you know $\binom{k+1}{2} = \sum_{i=1}^k i$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .