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.
