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$ 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. 
 A: 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.
A: 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.
