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

I think the definition is technically imprecise. The second property is correct, though it's often stated that if $n \in T$ then $n + 1 \in T$. The first property technically is not correct since we never require a base case of $n = 0$: some statements work only for, say, integers at least $2$. I do think it's useful to think of $T$ as a subset of $\mathbb{N}$ to symbolize that we could be talking about all natural numbers (assuming we start with $0$ or $1$, depending on how you define $\mathbb{N}$) or all naturals after some point. — , Nov 18 '18 at 00:54
where property 2 is if n is in T then n+1 is in T. This just seems more useful to me, and the one stated above to me seems more unclear — Carlos Bacca, Nov 18 '18 at 01:02

score 1 · Accepted Answer · answered Nov 18 '18 at 00:57

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.

answered Nov 18 '18 at 00:57

Mohammad Riazi-Kermani

68,728

Marcelo · Answer 2 · 2018-11-18T01:20:39.960

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$)

Steven Alexis Gregory · Answer 3 · 2019-05-15T22:47:00.000

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.

Induction definition

3 Answers3