Proof by mathematical induction (conditional statements)

Question

Suppose we need to prove a statement of the form $$\forall n\in\mathbb{N}(P(n)\to Q(n))$$ where $P(n)$ and $Q(n)$ are propositions using mathematical induction. Say for the base case $n=1$ it is true. Let $n=k>1$ and assume the statement is true (inductive hypothesis), that is $P(k)\to Q(k)$ is valid. If we are able to show that $P(k)\to P(k+1)$ and $Q(k)\to Q(k+1)$ would this be sufficient to conclude $$(P(k)\to Q(k))\to(P(k+1)\to Q(k+1))$$

Answer 1

If you replace $P(k)$, $P(k+1)$, $Q(k)$, and $Q(k+1)$ by $A,B,C,D$, your question amounts to whether the following is tautologically true: Does $A \to B$, $C \to D$, $A \to C$ imply $B \to D$? Or, if you like symbols, is $$\bigl((A \to B) \,\, \& \,\, (C \to D) \,\, \& \,\, (A \to C)\bigr) \to (B \to D) $$ a tautology?

The answer is no: take $B=T$, $D=F$, $C=F$, $A=F$. Then $A \to B$, $C \to D$, and $A \to C$ are true but $B \to D$ is false.

Answer 2

On principle, there is a misconception here. At the step $n=k+1$, you don't infer $P(k+1)$ from $P(k)$, you assume $P(k+1)$. Then, you use $P(k)\rightarrow Q(k)$ and $P(k+1)$ to infer $Q(k+1)$.

Answer 3

No.

Counterexample:

$P(k) \to Q(k)$ is true with $P(k), Q(k)$ false.

$P(k) \to P(k+1)$ may give you $P(k+1)$ true. $Q(k) \to Q(k+1)$ may give you $Q(k+1)$ false.

But $P(k+1) \to Q(k+1)$ does not hold then.

Answer 4

Look at what you'd really be proving -- you're applying induction to $P $ and $Q $ independently. If that worked and the base case wasn't trivial (that is, $P (1) \rightarrow Q (1) $ held because $P (1) $ and $Q (1) $ were both true) then you'd have proved by induction that $\forall k P(k) $ and $\forall k Q (k) $, which is probably not true.

Answer 5

If we are able to show that $P(k)\to P(k+1)$ and $Q(k)\to Q(k+1)$ would this be sufficient to conclude $$(P(k)\to Q(k))\to(P(k+1)\to Q(k+1))$$

Almost. It would be sufficient to prove $P(k+1)\to P(k)$ and $Q(k)\to Q(k+1)$. I don't know how useful that would be in practice, though.