1. ## Induction.

Hey everyone.

I'm having a little trouble understanding why it is that proof by induction constitutes as proof. If anyone could spare a little of their time and discuss this with me, I'd be much obliged.

Here's my understanding...

I was given this Theorem from my abstract algebra text (I know, i'm studying abstract and I can't even prove using induction...I'm screwed). The concepts of the algebra are easy to master, but I'm american, so I've never been instruced in the art of proof.

Theorem:

Let $\displaystyle S$ be a set of positive integers with the properties

a) $\displaystyle 1\in{S}$
b) whenever the integer $\displaystyle k\in{S}$, then $\displaystyle k+1\in{S}$ must also be in $\displaystyle S$.

Then $\displaystyle S$ is the set of all positive integers.

O.K. So, the book goes on to prove this theorem by employing the Well-Ordering Principle. I understand the proof, but I'm a little fuzzy on why this theorem allowa us to verify that certain relations are true for all $\displaystyle n\in{S}$.

Let's talk guys.

3. I am not sure I understand your problem...

I'm having a little trouble understanding why it is that proof by induction constitutes as proof.
Because induction is a theorem. In fact, you provided its statement in your post. This theorem has a proof; again, you said you understand it. Invoking proved theorems in other proofs is legitimate.

I'm a little fuzzy on why this theorem allowa us to verify that certain relations are true for all $\displaystyle n\in{S}$.
First, you probably mean, "to verify that certain relations are true for all positive integers". The induction theorem has the form, "For all S, if ..., then S is the set of positive integers". So unless one defines his/her own set S in order to apply the induction theorem to it, there is no S; certainly there is no S that is universally accepted.

Here is how induction theorem is applied. Suppose $\displaystyle S = \{n\in\mathbb{Z}^+ \mid 1 + \dots + n = n (n + 1) / 2\}$. Obviously, $\displaystyle S\subseteq\mathbb{Z}^+$. We would like to show that $\displaystyle \mathbb{Z}^+\subseteq S$. One way to approach this is to fix some $\displaystyle n\in\mathbb{Z}^+$ and to try to show

$\displaystyle 1 + \dots + n = n (n + 1) / 2$ (*)

directly. On the other hand, one can apply the induction theorem. This reduces the task to proving two facts: $\displaystyle 1\in S$ and $\displaystyle \forall k\in\mathbb{Z}^+, k\in S\to k+1\in S$.

What have we gained in the second approach? Here we also have to prove $\displaystyle k+1\in S$ for an arbitrary k, i.e.,

$\displaystyle 1 + \dots + k + 1 = (k+1)(k + 2) / 2$ (**)

However, compared to (*), we have a powerful induction hypothesis at our disposal:

$\displaystyle 1 + \dots + k = k (k + 1) / 2$

This makes proving (**) much easier than proving (*).

4. ok. So, let me try and tell me if there are any flaws in my thinking.

We would like to show by induction that $\displaystyle 1+2+...+(n-1)+n=\frac{n(n+1)}{2}$.

So, let $\displaystyle S$ be the be a subset of the natural numbers such that $\displaystyle 1+2+...+(n-1)+n=\frac{n(n+1)}{2}$ is a true statement.

Or, $\displaystyle S=\{n\in\mathbb{Z_+}|1+2+...+(n-1)+n=\frac{n(n+1)}{2}\}$

So, by inspection we see that $\displaystyle 1\in{S}$.

Now we nee to show that if $\displaystyle k\in{S}$, then $\displaystyle k+1\in{S}$.

Now assume that $\displaystyle k\in{S}$. Then we have

$\displaystyle 1+2+...+(k-1)+k=\frac{k(k+1)}{2}$.

If we add $\displaystyle k+1$ to both sides we get

$\displaystyle 1+2+...+(k-1)+k+(k+1)=\frac{k(k+1)}{2}+(k+1)$. But, The right hand side is equivalent to

$\displaystyle \frac{(k+1)[(k+1)+1]}{2}$ which is exactly what we would expect for the sum of the first $\displaystyle k+1$ elements.

Therefore, $\displaystyle S=\mathbb{Z_+}$

5. Touché.