1. ## mathematical induction?

Hi, not sure if this is advanced enough for this sub forum or not. But alas I have a problem, that problem is 'the maths of induction'. I've looked through books and the net, there doesn't seem to be:

A) Many learning resources on this
B) Any resource that explains this in a way I can understand

My lecturer has not seen fit to spend much time on it either. So here are my (3) problems:
Prove by mathematical induction that
1+2+3+…..+n = &#189;n(n+1)
For all integers n >= 1

Prove by mathematical induction that
1+3+5+ ….+ (2n-1) = n2
For all integers n >= 1

Prove by mathematical induction that
12+22+……+n2 = 1/6n(n+1)(2n+1)
For all integers n >= 1

Any help (answers and/or explanations) from the wise people of this forum, will be very welcome.

2. Hello, Sarah!

There are three steps to an Inductive Proof.

(1)Show that $\displaystyle S(1)$ is true.
. . That is, that the statement is true for $\displaystyle n = 1$.
(2) Assume that $\displaystyle S(k)$ is true.
. . That is, assume the statement is true for $\displaystyle n = k$.
(3) Proof that $\displaystyle S(k+1)$ is true.
. . Use $\displaystyle S(k)$ to show that the statement is true for $\displaystyle n = k+1$.

Prove by Induction that:
. . $\displaystyle 1 + 2 + 3 + \cdots + n\:=\:\frac{n(n+1)}{2}$
(1) Verify $\displaystyle S(1)$.
. . $\displaystyle S(1) \:=\:1 \:=\:\frac{(1)(2)}{2}$ . . . True.

(2) Assume $\displaystyle S(k)\!:\;\;1 + 2 + 3 \cdots + k \:=\:\frac{k(k+1)}{2}$

At this point, I write out the statement $\displaystyle S(k+1)$ just to get a look at it.
This is the statement we want to prove, so it's nice to know what it looks like.

Replace $\displaystyle k$ with $\displaystyle k+1\!:\;\;1 + 2 + 3 + \cdots + (k+1) \:=\:\frac{(k+1)(k+2)}{2}\quad\Leftarrow\;\text{ S(k+1)}$

(3) Start with $\displaystyle S(k)\!:\;\;1 + 2 + 3 + \cdots + k \:=\:\frac{k(k+1)}{2}$

Add $\displaystyle k+1$ to both sides:
. . $\displaystyle 1 + 2 + 3 + \cdots + k + (k+1) \:=\:\frac{k(k+1)}{2} + (k+1)$

The left side is the left side of $\displaystyle S(k+1)$.
We must show that the right side is the right side of $\displaystyle S(k+1)$.

The right side is: .$\displaystyle \frac{k(k+1)}{2} + (k+1) \:=\:\frac{k(k+1)}{2} + \frac{2(k+1)}{2}$

. . $\displaystyle = \:\frac{k^2 + k}{2} + \frac{2k + 2}{2}\:=\:\frac{k^2 + 3k + 2}{2} \:=\:\frac{(k+1)(k+2)}{2}$ . . . There!

We have shown that: .$\displaystyle 1 + 2 + 3 + \cdots + (k+1) \:=\:\frac{(k+1)(k+2)}{2}\quad\Leftarrow\text{ This is S(k+1)}$

Therefore: .$\displaystyle 1 + 2 + 3 + \cdots + n\:=\:\frac{n(n+1)}{2}$ for all natural numbers $\displaystyle n$.

3. Theory
Mathematical Induction on the Natual Integers is the 5th Axiom in the Peano Axioms of Arithmetic. Without going into the details of how it can be proved by set theory axioms we will simply state the result. Let $\displaystyle S$ be a subset of $\displaystyle \mathbb{N}$ which satisfies $\displaystyle 1\in S$ and if $\displaystyle k\in S$ then $\displaystyle k+1 \in S$. Conclusion: $\displaystyle S=\mathbb{N}$.

The general idea is like this.... $\displaystyle 1\in S$ then by the hypothesis $\displaystyle 1+1=2\in S$. But then by the hypothesis $\displaystyle 2+1=3\in S$ and thus on.... Hence we have all the integers.

I will do the most classical example:
$\displaystyle 1+2+...+n=\frac{n(n+1)}{2}$ (*).
We want to show this is true for any natural number $\displaystyle n$. Meaning if $\displaystyle S$ is the set of all natural numbers that satisfy this equation, we want to show $\displaystyle S=\mathbb{N}$. The typical way of doing this is by mathematical induction.
We need to show two things:
1)$\displaystyle 1\in S$. Meaning $\displaystyle 1$ satisfies equation (*).
2$\displaystyle k\in S\to k+1\in S$. Meaning if a natural number satisfies (*) then so does the one after that.

Again these two conditions are extremely important you cannot have one without the other.

We check condition #1, certainly,
$\displaystyle 1=\frac{1(2)}{2}=1$
Thus, $\displaystyle 1\in S$.
We check condition #2, let $\displaystyle k$ satisfy (*) that is,
$\displaystyle 1+2+...+k=\frac{k(k+1)}{2}$
Add $\displaystyle k+1$ to both sides (you will see why),
$\displaystyle 1+2+...+k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1) (k+2)}{2}$.
Ah! $\displaystyle k+1$ also satisfies (*).
Thus, $\displaystyle k\in S\to k+1\in S$.
Thus, by mathematical induction $\displaystyle S=\mathbb{N}$.
Q.E.D.

Typical Approach
In general people do not do all of what I said above, because it is too lengthy.
They just show:
1)$\displaystyle 1$ works.
2)If $\displaystyle k$ works then $\displaystyle k+1$ works.

In that case #1 is true because:
$\displaystyle 1=\frac{1(2)}{2}$.

And #2 is true because:
$\displaystyle 1+2+...+k=\frac{k(k+1)}{2}$
Add $\displaystyle k+1$ to get,
$\displaystyle 1+2+...+k+(k+1)=\frac{(k+1)(k+2)}{2}$ (algebra omitted).

And then proof complete. Again this is not a formal mathematical approach but this is usually done to save time.