Follow-up question on mathematical induction with arbitrary base case

Question

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?

Answer 1

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