Question on inductive proof structure involving a conditional statement

Question

Say we have an inductive proof that is structured as follows:

If $P(k)$ then $Q(k)$ where $P$ and $Q$ are some arbitrary predicates and $k$ is the subject of those predicates.

Now, suppose we go through a base case and get to our inductive step.

We are going to assume $P(k)\Rightarrow Q(k)$ (call this the inductive hypothesis) is true for values greater than or equal to our base case and try to show $P(k+1)\Rightarrow Q(k+1)$. Now it is clear to me that we may use our inductive hypothesis in our proof as granted... but what about the antecedent of the next step we are trying to prove? That is I can assume $P(k)\Rightarrow Q(k)$, but may I also assume $P(k+1)$?

For instance suppose the statement $P(k)$ were to be there exist two integers $a$ and $b$ such that $a\leq x_1,x_2,x_3,...,x_k \leq b$ do I get to assume $a \leq x_1,x_2,x_3,...,x_k,x_{k+1}\leq b$ in my inductive step?

Basically I know $P(k)\Rightarrow P(k+1)$ is the general structure of an inductive proof. But what about when we have conditional statments like $(P(k)\Rightarrow Q(k))\Rightarrow(P(k+1)\Rightarrow Q(k+1))$?

Answer 1

Yes, that works. The general pattern for (weak mathematical) induction is:

$(\varphi(0) \land \forall k (\varphi(k) \rightarrow \varphi(k+1)) \rightarrow \forall k \varphi(k)$

for any formula $\varphi(k)$.

So, with $\varphi(k)$ being the formula $ P(k) \rightarrow Q(k)$, you get what you want.

And yes, for the inductive step, you assume the inductive hypothesis $P(k) \rightarrow Q(k)$, and try to show $P(k+1) \rightarrow Q(k+1)$, and to show that, you will probably want to assume $P(k+1)$ and try to get to $Q(k+1)$.

Finally, don't forget the base case, i.e. $P(0) \rightarrow Q(0)$ (or, if the base case is $k=1$, $P(1) \rightarrow Q(1)$), for which you probably want to do a conditional proof as well (i.e. Assume $P(0)$, and try and get to $Q(0)$.