# Thread: Proving the Hypothetical Syllogism using Induction

1. ## Proving the Hypothetical Syllogism using Induction

Hi All,

First post here. thanks for the help in advance!

Okay first, the problem:

In Logic, the hypothetical syllogism says that given three statements, P, Q, and R, the hypothesis P $\displaystyle \rightarrow$ Q and Q $\displaystyle \rightarrow$ R logically imply P $\displaystyle \rightarrow$ R. Symbolically written ((P $\displaystyle \rightarrow$ Q) ^ (Q $\displaystyle \rightarrow$ R) $\displaystyle \Rightarrow$ (P $\displaystyle \rightarrow$ R))
Use induction to show that, given n statements ($\displaystyle ^A{1}$, $\displaystyle ^A{2}$, .... $\displaystyle ^A{n}$) that ($\displaystyle ^A{1}$ $\displaystyle \rightarrow$ $\displaystyle ^A{2}$) ^ ($\displaystyle ^A{2}$ $\displaystyle \rightarrow$ $\displaystyle ^A{3}$ ^ ... ^ ($\displaystyle ^A{n-1}$ $\displaystyle \rightarrow$ $\displaystyle ^A{n}$) $\displaystyle \Rightarrow$ ($\displaystyle ^A{1}$ $\displaystyle \rightarrow$ $\displaystyle ^A{n}$) for n $\displaystyle \geq$ 2

The problem I am having is that I am not sure how to work out an equation from this statement that I can start to use induction on. Also, I'm not sure if I should try to prove this using an inequality expression or an = expression. It would seem to me that an inequality would make more sense in an implication of this sort, but I am anything but positive on it.

I tried subbing in an arbitrary x for $\displaystyle ^A{1}$, and assigning (x+1) to $\displaystyle ^A{2}$, and using $\displaystyle ^A{1}$ $\displaystyle \leq$ $\displaystyle ^A{2}$, but my problem exploded and became unreasonable.

Can someone please help me find what recursive function or sum equation I should start with? I should be able to solve the proof from there with mathematical induction (also, do you suppose strong induction or standard will work in this case?)

Thanks again all!

-EDIT-

Here is what I have done so far. I think it proves this is true for $\displaystyle ^A{n}$ when f(n)=n, but is this all I need to do? What about cases where f(n) is equal to something other than just n?

let $\displaystyle ^A{n}$ = f(n) where:
f(1) = 1
f(n) = n for n $\displaystyle \geq$ 2

Step 1: (Base case) LHS $\displaystyle ^A{2}$ = 2, and RHS f(2) = 2
Step 2: (Show $\displaystyle ^A{n+1}$ = f(n+1)
$\displaystyle ^A{n+1}$ = f(n+1)
$\displaystyle ^A{n+1}$ = n+1 $\displaystyle \leftarrow$ induction step

so there is the proof for $\displaystyle ^A{n+1}$, but something just feels wrong about this. have I solved this problem, or am I missing something here?