sum(n) = n*(n+1)/2
-
Base case: Is it true for
sum(0)
?sum(0) = 0(0+1)/2 = 0
Yes!
-
Inductive case: Assume
sum(i) = i(i+1)/2
is the sum of integers from0
toi
. Then the sum of all integers from0
toi+1
is just the sum from0
toi
(which is justsum(i)
) plusi+1
sum(i) + (i+1) = i(i+1)/2 + (2i + 2)/2 <-- by mult. & div. by 2 = (i(i+1) + 2i + 2)/2 <-- by Distributive Law = (i^2 + 3i + 2)/2 = (i+1)(i+2)/2 <-- factoring (i^2 + 3i + 2) = (i+1)((i+1)+1)/2 = sum(i+1)
So we've shown the base case, and we've shown that the statement
sum(i)
is the sum of integers from 0
to i
implies the statement
sum(i+1)
is the sum of integers from 0
to i+1
.
So, by the principle of induction, we have that for all natural numbers n
, sum(n)
is the sum of integers from 0
to n
, where
sum(n) = n(n+1)/2