Induction definition

Question

Suppose $T$ is a subset of $N$

Property 1: $0 \in T$, and

Property 2: For every natural number $n \ge 1$, if $n − 1 \in T$ then $n \in T$

Hi this is how POI is introduced in my notes and then it is stated in the more common way. Im wondering if this version is really useful at all i cant see the point in stating it this way?

Maybe you can help me thanks

Answer 1

Yes that is a valid definition of induction method .

Probably you worry about the starting point of $0$ instead of $1$ because usually they start with $n=1$

You can start at any integer and go from there depending on the problem.

Answer 2

You can enunciate the principle of finite induction (PFI) in many ways! A nice approach that helps visualizing equivalence between different statements about PFI is to imagine that you are going up stairs.

Property one says simply where you begin your rise. You could prove that some math statements works for all $n\geq 2$ and induction is used there too! For example, Fermat's Last Theorem! (Although that its not just induction which solves it hehehe)

Property two says just how you walk up the stairs. The main point is that from where you started PIF guarantees you will go through all steps up the stairs.

Saying "if its valid for $n-1$ then it works too for $n$, for all $n$" also guarantees our climb because you DO know that you got in step $0$ (by property one) and you can use $0=n-1$ and prove that you ALSO can go to step $1=n$... and so one. That's exactly the same thing that saying that "if its valid for $n$ then it works too for $n$, for all $n+1$"... you just name $0=n$ and then $1=n+1$ and so on.

The first way maybe is more "esthetically good" because you were asked to prove some statement for all $n$ and finishes your proof by showing that some property is also valid for some generical $n$ (instead of some generical $n+1$)

Answer 3

What I like about this POI is that it focuses on set membership and not equations. This is what I mean. Consider the equation $$\forall n \in \mathbb N, \sum_{i=0}^n i = \dfrac 12n(n+1)\tag{1}$$ A proof using your version of POI would go as follows.

Let $\displaystyle \mathbf T = \left\{n \in \mathbb N: \sum_{i=0}^n i = \dfrac 12n(n+1)\right\}$. (Note $\mathbf T \subseteq \mathbb N.$)

STEP $1$. Since $\sum_{i=0}^0 i =0= \dfrac 120(0+1)$, then $0 \in \mathbf T$.

STEP $2$. Suppose for some natural number, $n \ge 1$, that $n-1 \in \mathbf T$. Then $\displaystyle \sum_{i=0}^{n-1} i = \dfrac 12(n-1)(n)$. So \begin{align} \sum_{i=0}^{n} i &= \sum_{i=0}^{n-1} i + \sum_{i=n}^{n} i \\ &= \dfrac 12(n-1)(n) + n \\ &= \dfrac 12(n^2 - n + 2n) \\ &= \dfrac 12 n(n+1). \end{align}

Hence $n-1 \in \mathbf T \implies n \in \mathbf T$.

It follows, from POI, that $\mathbf T = \mathbb N$. Hence equation $(1)$ is proved.