Exercise 6.5.11 (Velleman's How to Prove It) 
Suppose
$R$ is a relation on set $A$.
$S$ is the transitive closure of $R$.
$\forall n \in \mathbb{Z}^+ (J_n = \{0,1,2,\dots, n\})$.  
Let $a,b \in A$.
$f: J_n \rightarrow A$ is an $R$-path from $a$ to $b$ of length $n$ if
  $f(0)=a \land f(n)=b \land \forall i < n (f(i), f(i+1)) \in R$.
  If, in addition, $f$ is one-to-one, the $R$-path is said to be simple.
Prove $\forall n \in \mathbb{Z}^+ (R^n \setminus i_A \subseteq \{ \exists \text{simple $R$-path from $a$ to $b$ of length $\leq n$}\})$
  For convenience, let $S_n = \{ \exists \text{simple $R$-path from $a$ to $b$ of length $\leq n$}\}$.
  So, we need to prove  $\forall n \in \mathbb{Z}^+ (R^n \setminus i_A \subseteq S_n)$, where $i_A$ is the identity relation on $A$.

My attempt (using ordinary induction):
Base case: n=1.
Suppose arbitrary $(a,b) \in R^1 \setminus A$.
$(a,b) \in R \land (a,b) \notin i_A$, thus, $a \neq b$.
Let $f = \{(0,a), (1,b)\}$, then $f(0)=a \land f(n=1)=b \land \forall i < n=1 (f(i), f(i+1)) \in R$.
In addition, since $a \neq b$, $f$ is one-to-one, so, $f$ is a simple $R$-path from $a$ to $b$ of length $n$. Thus, $(a,b) \in S_1$.
Since $(a,b) \in R^1 \setminus A$ is arbitrary, $R^1 \setminus A \subseteq S_1$.
Induction step:
Suppose arbitrary $n \in \mathbb{Z}^+$.
Suppose $R^n \setminus i_A \subseteq S_n$. Need to show $R^{n+1} \setminus i_A \subseteq S_{n+1}$.
Suppose arbitrary $(a,c) \in R^{n+1} \setminus i_A$.
$(a,c) \in R^{n+1} \land (a,c) \notin i_A$, so, $a \neq c$, and
$\exists b \in A ( (a,b) \in R^n \land (b,c) \in R^1)$.
$\vdots$
This is where I stuck. 
The solutions I found hinted that we can first prove that $a \neq b \land b \neq c$ to proceed. I tried proof by contradiction (by assuming $a=b \lor b=c$) but found nothing to contradict with.
So, my question now is how to show $a \neq b \land b \neq c$? 

In induction step we assume that $$(a,c) \in R^{n+1}\setminus i_A \iff (a,c) \in R \circ R^n \land a \neq c,$$ so we can have some $b \in A$, such that $(a,b) \in R^n$ and $(b,c) \in R$. Thus by the inductive hypothesis there is simple R-path of at most length n from a to b and simple R-path of at most length 1 from b to c. Therefore we can have the union of these R-paths as R-path from a to c of at most length n+1.
If $a=b \lor b=c$, then by the inductive hypothesis we still can have a simple R-path from a to c, but of length n. Since $n < n+1$ then our R-path meets requirement of being at most of length $n+1$.
