Prove that 1+2+3++n = sum_k=1ⁿ k = (n(n+1))/(2), n 1.

Here is the proof for using the Principle of Mathematical Induction.

1. Prove that $1+2+3+\dots+n = \sum_{k=1}^{n} k = \frac{n(n+1)}{2}$, $\forall n \ge 1$.

Let $P(n)$ be the statement $1+2+3+\dots+n = \frac{n(n+1)}{2}$.

• Base Case (n=1): LHS $= 1$ RHS $= \frac{1(1+1)}{2} = \frac{1(2)}{2} = 1$ Since LHS = RHS, $P(1)$ is true.

• Inductive Hypothesis: Assume $P(m)$ is true for some positive integer $m$. That is, assume $1+2+3+\dots+m = \frac{m(m+1)}{2}$.

• Inductive Step: We need to prove that $P(m+1)$ is true, i.e., $1+2+3+\dots+(m+1) = \frac{(m+1)((m+1)+1)}{2} = \frac{(m+1)(m+2)}{2}$. Consider the LHS of $P(m+1)$:

  $$1+2+3+\dots+m+(m+1)$$

  By the Inductive Hypothesis, substitute $1+2+3+\dots+m = \frac{m(m+1)}{2}$:

  $$\frac{m(m+1)}{2} + (m+1)$$

  Factor out $(m+1)$:

  $$(m+1) \left( \frac{m}{2} + 1 \right)$$ $$(m+1) \left( \frac{m+2}{2} \right)$$ $$\frac{(m+1)(m+2)}{2}$$

  This is the RHS of $P(m+1)$. Thus, $P(m+1)$ is true.

By the Principle of Mathematical Induction, $P(n)$ is true for all $n \ge 1$.
The proof is complete.