notationproof-writing
For a conclusion for proof by induction, I usually write since the base case is true and $p(k)\implies p(k+1)$, then by the principle of mathematical induction, $p(n)$ is true for all positive integers, for example.
However, when doing proofs involving second order recurrence relations, I need to use the phrase: “if p(k) is true and p(k+1) is true, then p(k+2) is true”. How can I write this phrase using $\implies$?
If $P(n_0)$ is false then the implication $P(n_0) \implies P(n_0+1)$ is true (vacuously, as you've pointed out), however, we cannot deduce the truth or otherwise of $P(n_0+1)$ in this case.
The hardest part in a proof by induction is proving $P(n) \implies P(n+1).$ If you've proved this, then all you have to do is find a suitable $n_0$ such that $P(n_0)$ is true. If $P(n_0)$ is false, but $P(n) \implies P(n+1)$, then pick a different value for $n_0$ (assuming that one exists). If you can find just one such $n_0$ (and if you've proved that $ \forall n, P(n) \implies P(n+1)$, then $P(n)$ is true for all $n \geqslant n_0$, by the principle of mathematical induction.
In this case, pick a different value of $n_0$ until $P(n_0)$ is true.
Regarding your last sentence, if $P(n_0)$ is true and $P(n) \implies P(n+1)$, then, by the property of implication, $P(n_0+1)$ is true, as is $P(n_0+2), P(n_0+3), ...$, so you'd never have $P(n_1)$ being false (for any $n_1 \geqslant n_0$)!
Property $WOP$ is Well-Ordering Principle.
Property $MI$ is Mathematical Induction.
(Exercise 1) Statement $S$ is given with a Proof , hence we are given $WOP \implies S$.
We are asked to show that $MI \implies S$.
(Exercise 2) Statement $S$ is given with a Proof , hence we are given $MI \implies S$.
We are asked to show that $WOP \implies S$.
(Exercise 3) We are asked to show that $WOP \iff MI$.
While (Exercise 1) is the OP Query in the text book $3^{rd}$ Edition , we might also consider (Exercise 2) which might not be given in that text book , though (Exercise 3) is there in Newer Editions & all 3 Claims are essentially the Same Idea.
More-over , (Exercise 3) is the Best Way to state that Core Idea.
That can be seen with this intuitive thinking :
(Exercise 1) $[ (WOP \implies S) \land (WOP \iff MI) ] \implies (MI \implies S)\tag{X1}$
(Exercise 2) $[ (MI \implies S) \land (MI \iff WOP) ] \implies (WOP \implies S)\tag{X2}$
We can also see it using logical manipulation.
We are simply assuming & using (Exercise 3) here.
Proving (Exercise 3) is simple enough : Check out https://brilliant.org/wiki/the-well-ordering-principle/#equivalence-with-induction
I am skipping the Proof here , because OP says that the Proof is known & that Proof is not what the Question is about.
OP : To clarify, I know that the well-ordering principle is equivalent to weak mathematical induction; this is not what I am asking.
Proof Over-view : We show that $WOP \implies MI$ & $MI \implies WOP$ , to then conclude that $WOP \iff MI$.
Naturally , the Newer Edition is better focused on the Core Issue.
OP : Another way to state the problem above is: if I can write a valid proof for a statement using the well-ordering principle, can I write a valid proof for the same statement that uses weak mathematical induction without knowing the well-ordering principle?
Yes , we can achieve that with the Equivalences given by (X1) & (X2) , where we can use the Proof Method itself , while not invoking WOP.
OP : I am not sure how to answer this and could not find the answer online.
In general , we just have to show the Equivalence between the two.
Even though we have the Stronger Claim that $MI \iff WOP$ here , within the Context of the Exercise , we have to just show $MI \implies WOP$.
Basic Out-line : Prove WOP with MI , then use the given Proof that "$WOP \implies S$" to get the Chain "$[ MI \implies WOP ] \land [ WOP \implies S ]$" to eventually conclude that "$MI \implies S$"
Diagram & Analogy :
When WOP gives S , we can start at MI , then show WOP & then show S. Hence MI gives S.
When MI gives S , we can start at WOP , then show MI & then show S. Hence WOP gives S.
Here is one analogy to see what is going on.
P1 : When $x$ is Even number , then $x^3+5$ is not divisible by $8$.
P2 : When $x=2y$ , then $x^3+5$ is not divisible by $8$.
Both are true because "$x$ is Even" $\iff$ "$x=2y$" & we have to use that fact (Directly or not) : We can not escape that Equivalence.
Here is one non-mathematical analogy :
Prove that "X1 : US President can press the nuclear bombing button"
Prove that "X2 : Biden can press the nuclear bombing button"
Prove that "X3 : White House Boss can press the nuclear bombing button"
Every Proof of X2 will utilize the fact (Directly or not) that the Authority lies with US President who is "Currently" Equivalent to Biden.
Every Proof of X3 will utilize the fact that White House Boss is Biden who is "Currently" US President.
We can not escape that Equivalence.
Here is one last scientific analogy :
Suppose we have Chemical Ingredient X.
Suppose liquid water is necessary to convert X to Chemical Y through a well-known reaction.
Suppose ice will not react with X.
Prove that we can make Chemical Y with Chemical Ingredient X & ice , even though ice is inert & will not react with X.
Proof : Heat the ice to make liquid water. Then use that water in the well-known reaction to convert X to Y.
We have used the inert ice to convert X to Y !
That occurs because ice (WOP) is equivalent to water (MI) !
We can easily convert X (Premises) to Y (Conclusion S) with that Equivalence
More-over , we can not escape that Equivalence.
Best Answer
How about
$p(k)\wedge p(k+1)\Rightarrow p(k+2)$
meaning "if $p(k)$ and $p(k+1)$ then $p(k+2)$"