Proof:Σi = n(n+1)/2

From CS2800 wiki


For all [math]n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], [math]\sum_{i=0}^n i = \frac{n(n+1)}{2} [/math]
Proof:
We prove this statement by weak induction on [math]n [/math]. Let [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math]

be the statement "[math]\sum_{i=0}^n i = \frac{n(n+1)}{2} [/math]". We will show [math]P(0) [/math] and [math]P(n+1) [/math] (assuming [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math]).

Aside: Note that [math]P(n) [/math] does not include the "for all n". To see why, imagine that it did. Then [math]P(7) [/math] would say "for all 7, ...",
Aside: A common mistake people make when writing inductive proofs, especially those involving formulas, is to think of [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math] as a 'number' and not a statement. If you find yourself writing [math]P(n) + n = 7 [/math], you are doing something wrong! Plugging this in would give [math]\left(\sum_{i=0}^n i = \frac{n(n+1)}{2}\right) + n = 7 [/math] which doesn't make sense.

In the case where [math]n = 0 [/math], the left hand side and the right hand side are both 0.

Now, to see [math]P(n+1) [/math], first assume [math]P(n) [/math]. We want to show [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n+1)} [/math], i.e. that [math]\sum_{i=0}^{n+1} i = \frac{(n+1)(n+2)}{2} [/math]. We compute:

[math]\begin{aligned} \sum_{i=0}^{n+1} i &= 0 + 1 + \cdots + n + (n+1) && \text{by definition} \\ &= \left(0 + 1 + \cdots + n\right) + (n+1) && \href{/cs2800/wiki/index.php?title=Algebra&action=edit&redlink=1}{\text{arithmetic}} \\ &= \frac{n(n+1)}{2} + (n+1) && \href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{\text{by P(n)}} \\ &= \frac{n(n+1) + 2n + 2}{2} = \frac{(n+1)(n+2)}{2} && \href{/cs2800/wiki/index.php/Arithmetic}{\text{algebra}} \end{aligned} [/math]

as required.

Aside: This proof uses a common pattern in inductive proofs (and in many other proofs too!): in the first few steps, we take what we want to show, and manipulate it so that we can use what we know ([math]P(n) [/math] in this case). If you get stuck, it's always good to look at what you've assumed already and try to find a way to apply it.