# Prove that sum_(i=1)^n ((i),(2))=((n+1),(3)) for all n>=2

Prove that $\sum _{i=1}^{n}\left(\begin{array}{c}i\\ 2\end{array}\right)=\left(\begin{array}{c}n+1\\ 3\end{array}\right)$
$\mathrm{\forall }n\ge 2$

You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

crocolylec

Step 1. Definitions
Definition combination
$nCr=\left(\begin{array}{c}n\\ r\end{array}\right)=\frac{n!}{r!\left(n-r\right)!}$
with $n!=n×\left(n-1\right)×\cdots ×2×1$.
Pascal's equation
$\left(\begin{array}{c}n+1\\ k\end{array}\right)=\left(\begin{array}{c}n\\ k\end{array}\right)+\left(\begin{array}{c}n\\ k-1\end{array}\right)$
Step 2. Solution
To proof: $\sum _{i=1}^{n}\left(\begin{array}{c}i\\ 2\end{array}\right)=\left(n+1\right)$ for all positive integers.
Proof by induction
Let P(n) be the statement "$\sum _{i=1}^{n}\left(\begin{array}{c}i\\ 2\end{array}\right)=\left(n+1\right)$".
Basis step. $n=2$
$\sum _{i=1}^{n}\left(\begin{array}{c}i\\ 2\end{array}\right)=\sum _{i=1}^{2}\left(\begin{array}{c}i\\ 2\end{array}\right)=\left(\begin{array}{c}i\\ 2\end{array}\right)+\left(\begin{array}{c}2\\ 2\end{array}\right)=0+1=1$
$\left(\begin{array}{c}n+1\\ 3\end{array}\right)=\left(\begin{array}{c}2+1\\ 3\end{array}\right)=\left(\begin{array}{c}3\\ 3\end{array}\right)=1$
Thus P(2) is true.
Inductive step. Let P(k) be true.
$\sum _{i=1}^{k}\left(\begin{array}{c}i\\ 2\end{array}\right)=\left(\begin{array}{c}k+1\\ 3\end{array}\right)$
We need to proof that $P\left(k+1\right)$ is true.
$\sum _{i=1}^{k+1}\left(\begin{array}{c}i\\ 2\end{array}\right)$
$=\sum _{i=1}^{k+1}\left(\begin{array}{c}i\\ 2\end{array}\right)+\left(\begin{array}{c}k+1\\ 2\end{array}\right)$

Thus $P\left(k+1\right)$ is true.
Conclution. By the principle of methematical induction, P(n) is true for all positive integers n.