0
$\begingroup$

Note: This question has already been answered here Proving mathematical induction with arbitrary base using (weak) induction.

I was trying to 'reconstruct' at least one proof given in this question or to grasp the idea. I believe my main struggle is the setup and find something to even work with. I will summarize it here again in my own words.

Proposition: Let $n_0 \in \mathbb{N}=\lbrace0,1,2, \dots \rbrace$ be arbitrary and $A(n)$ be a property for $n \in \mathbb{N}$.
If $A(n_0)$ is true and $\forall n \geq n_0: A(n) \implies A(n+1)$ then $\forall n \geq n_0:A(n)$

This is something that can be shown by induction. However I am having great trouble with the setup of it. I could copy-paste what's already written in the linked question but I have no understanding about how they compose their statements there.

The Proposition above can be summarized as: Induction works for any base case $n_0 \in \mathbb{N}$, prove that.

  • So one setup they use in the linked question is the following. Let $Q$ be the statement $Q(n): n \geq n_0 \implies A(n)$. This makes somehow sense to me, because I read it as if $n \geq n_0$ is true, then $A(n)$ better be true as well.

But I don't see how it is linked to the proposition above, because the proposition uses much more than just that, it also makes use of that $\forall n \geq n_0: A(n) \implies A(n+1)$ so I can only guess that they make use of the transitive property of the implication (law of syllogism)

  • The second setup as suggested by Professor Brian M. Scott is to define $Q(n):A(n+n_0)$ which seems very counter intuitive to me. It might be a good trick but I have no idea how to work with it.

Let me try to work with the hint given by Brain M. Scott. Define $Q(n): A(n+n_0)$

$Q(0): A(n_0)$ and now I am already stuck. Does this expression direct me to go back up to the proposition and continue reading from there? If so, how is that supposed to complete the base case?

$\endgroup$
1
$\begingroup$

The "standard" expression of Induction principle is :

$(A(0) \land \forall n (A(n) \rightarrow A(n+1))) \rightarrow \forall n A(n)$.

In words :

if we can prove that "property" $A$ holds for $0$ and we can prove that : if it holds for a number $n$ whatever, then it holds also for its successor (i.e. $n+1$), then "property" $A$ holds for every natural numbers.

The "trick" with

Proposition : Let $n_0 \in \mathbb N = \{ 0,1,2,\ldots \}$ be arbitrary and $A(n)$ be a property for $n \in \mathbb N$. If $A(n_0)$ is true and $∀n \ge n_0 : A(n) \rightarrow A(n+1)$ then $∀n \ge n_0 : A(n)$

is quite simple; define a new property $A'(n) := A(n+n_0)$ and apply "normal" Induction.

For $n=0$, we prove $A'(0)$, which is $A(0+n_0)=A(n_0)$.

Then we prove ; $\forall n(A'(n) \rightarrow A'(n+1))$, which amount to : $\forall n \ge n_0(A(n) \rightarrow A(n+1))$.

Thus, by Induction we conclude with :

$\forall n A'(n)$,

which is : $\forall n \ge n_0 : A(n)$.

$\endgroup$
5
  • $\begingroup$ Thanks for your answer, I believe to understand this already better. The base case with the new defined property would be true by definition, because $A(n_0)$ is true. Do I read that right? Next I assume the Proposition to be true for our newly defined property $A'(n)=(An+n_0)$ and continue from there? $\endgroup$
    – Spaced
    Oct 5 '14 at 14:15
  • $\begingroup$ @Spaced - in general, we have to prove the base case also; but usually, it is a quite simple calculation. Having proved or verified the base case, YES, you have to prove the induction step for $A'$. Having done this, you can conclude that the property $A$ holds for all numbers "starting from" the base one. $\endgroup$ Oct 5 '14 at 14:20
  • $\begingroup$ I think what confuses me in your description is the phrase $A'(n) \to A'(n+1)$ which amount to $A(n) \to A(n+1)$ you mean that they have the same significance or that they are really the same? $\endgroup$
    – Spaced
    Oct 5 '14 at 14:28
  • $\begingroup$ @Spaced - I've written : "...which amount to : $∀n≥n_0(A(n)→A(n+1))$" and not $\forall n(A(n)→A(n+1))$ ... $\endgroup$ Oct 5 '14 at 14:34
  • $\begingroup$ I think I get it, I have to show more empathy to the quantors in order to understand this step :) $\endgroup$
    – Spaced
    Oct 5 '14 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.