Prove by induction that for $n\geq 3$, $p_1 \to p_2, p_2 \to p_3, \dots p_{n-1} \to p_n \implies p_1 \to p_n$

Question

I have proven the base case for $n=3$ by creating a truth table and verifying the implication. Now i need help with inducing a proof for every case. Please guide me on how i should approach this problem.

Answer 1

The induction step is to prove that

p1 → p2, p2 → p3, ..., p(n-1) → pn ⇒ p1 → pn
implies
p1 → p2, p2 → p3, ..., p(n-1) → pn, pn → p(n+1) ⇒ p1 → p(n+1).

First assume p1 → p2, p2 → p3, ..., p(n-1) → pn ⇒ p1 → pn.

Now assume p1 → p2, p2 → p3, ..., p(n-1) → pn, pn → p(n+1).

Show from those assumptions that p1 → pn
and subsequently p1 → p(n+1).

Pull it together to conclude
p1 → p2, p2 → p3, ..., p(n-1) → pn, pn → p(n+1) ⇒ p1 → p(n+1)

and finally the induction step.

Forget about that truth table stuff.
It is not a major part of logic.
The rules of inference are.
Use them.

Answer 2

Proof by induction is typically used to prove a statement about the natural numbers, or some subset thereof. For example, we may be proving $\forall n P(n)$ where $n \in \mathbb{N}$ and $P(n)$ is the statement $\sum_{i=0}^ni=\frac{n(n+1)}{2}$. In other words, we may be proving that for every $n \ge 0$, the sum of the first $n$ natural numbers is $\frac{n(n+1)}{2}$.

Proof by induction is organized into two steps:

$(1)$ In the basis step, you demonstrate that $P(n)$ is true for the least element in the domain you're working with. In the example above, we would want to show that $P(0)$ is true. So we work out $P(0)$, or $\sum_{i=0}^0i=0=\frac{0(0+1)}{2}=0$, and confirm that it is in fact true.

$(2)$ In the inductive step, the goal is to validly deduce the following statement: $P(k) \rightarrow P(k+1)$ where $k$ is some arbitrary number from the domain you're working with. This is typically accomplished by assuming the antecedent is true and then deriving the consequent. In other words, we assume that $P(k)$ is true, and then under that assumption we attempt to show that $P(k+1)$ is true.

Following the example above, I would assume $P(k)$, or $\sum_{i=0}^ki=\frac{k(k+1)}{2}$, is a true statement, and then my goal would be to derive $P(k+1)$, which is $\sum_{i=0}^{k+1}i=\frac{(k+1)[(k+1)+1]}{2}=\frac{(k+1)(k+2)}{2}$. I would do all this as follows:

$$P(k): \sum_{i=0}^ki = \frac{k(k+1)}{2}$$ $$\sum_{i=0}^ki + (k+1)= \frac{k(k+1)}{2} + (k+1)$$ $$\sum_{i=0}^{k+1}i= \frac{k(k+1)}{2} + \frac{2(k+1)}{2}$$ $$\sum_{i=0}^{k+1}i= \frac{k(k+1)+2(k+1)}{2}$$ $$\sum_{i=0}^{k+1}i= \frac{k^2 +k+2k+2}{2}$$ $$\sum_{i=0}^{k+1}i= \frac{k^2 +3k+2}{2}$$ $$\sum_{i=0}^{k+1}i= \frac{(k+1)(k+2)}{2}$$ $$P(k+1): \sum_{i=0}^{k+1}i= \frac{(k+1)(k+2)}{2}$$

Once you have completed the basis step and the inductive step, you are finished. By induction you may conclude that $\forall n P(n)$ is true (i.e. $P(n)$ is true for all $n$ in the domain you're working with). This is all possible because the inductive step shows that if the statement $P(n)$ is true for any arbitrary number $k$ in your domain, then it is also true for the very next number, $k+1$. Since in the basis step you show $P(n)$ is true for the first number in the domain, this infers that $P(n)$ is true for every number after the first number.