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

Question

Prove that $\sum_{i = 1}^{n} (\begin{matrix} i \\ 2 \end{matrix}) = (\begin{matrix} n + 1 \\ 3 \end{matrix})$
$\forall n \geq 2$

Answer 1

Step 1. Definitions
Definition combination
$n C r = (\begin{matrix} n \\ r \end{matrix}) = \frac{n!}{r! (n - r)!}$
with $n! = n \times (n - 1) \times \dots \times 2 \times 1$ .
Pascal's equation
$(\begin{matrix} n + 1 \\ k \end{matrix}) = (\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n \\ k - 1 \end{matrix})$
Step 2. Solution
To proof: $\sum_{i = 1}^{n} (\begin{matrix} i \\ 2 \end{matrix}) = (n + 1)$ for all positive integers.
Proof by induction
Let P(n) be the statement " $\sum_{i = 1}^{n} (\begin{matrix} i \\ 2 \end{matrix}) = (n + 1)$ ".
Basis step. $n = 2$
$\sum_{i = 1}^{n} (\begin{matrix} i \\ 2 \end{matrix}) = \sum_{i = 1}^{2} (\begin{matrix} i \\ 2 \end{matrix}) = (\begin{matrix} i \\ 2 \end{matrix}) + (\begin{matrix} 2 \\ 2 \end{matrix}) = 0 + 1 = 1$
$(\begin{matrix} n + 1 \\ 3 \end{matrix}) = (\begin{matrix} 2 + 1 \\ 3 \end{matrix}) = (\begin{matrix} 3 \\ 3 \end{matrix}) = 1$
Thus P(2) is true.
Inductive step. Let P(k) be true.
$\sum_{i = 1}^{k} (\begin{matrix} i \\ 2 \end{matrix}) = (\begin{matrix} k + 1 \\ 3 \end{matrix})$
We need to proof that $P (k + 1)$ is true.
$\sum_{i = 1}^{k + 1} (\begin{matrix} i \\ 2 \end{matrix})$
$= \sum_{i = 1}^{k + 1} (\begin{matrix} i \\ 2 \end{matrix}) + (\begin{matrix} k + 1 \\ 2 \end{matrix})$
$(\begin{matrix} k + 1 \\ 3 \end{matrix}) + (\begin{matrix} k + 1 \\ 2 \end{matrix}) Since P(k) is true$
$= (\begin{matrix} (k + 1) + 1 \\ 3 \end{matrix}) Pascal's identity$
Thus $P (k + 1)$ is true.
Conclution. By the principle of methematical induction, P(n) is true for all positive integers n.

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

Expert Answer

Not exactly what you’re looking for?

Relevant Questions