Now I get stuck in the proof of the hint in (d), I try to use induction to prove the hint. The base is $i=k+1$, after that I think I should prove $(a,b) \in R^{i-1}$ for $i < k+1$ with the assumption of $(a,b) \in R^i$. Then I am not sure what to do, I don't know how to use $(a,b) \in R^{k+1}$ into my calculation. In other words, I cannot find a helpful relationship between the $R^{k+1}$ and $R^i$ , and I guess I am not able to prove the conclusion without the help of $R^{k+1}$. I have considered this for a really long time, could anyone give me some advice?
Some conclusions that may be useful, while the third line is false
";" is defined as:
$R_1;R_2 = \{(a,c) : \textrm{there is a } b \textrm{ with }(a,b) \in R_1 \textrm{ and }(b,c) \in R_2\}$
I'll give it a shot. I may have something wrong, because I find that $R^{k-1}=R^k$. I am sure there are cleverer ways to do it as well, but:
I claim that $$ R^n = I \cup R \cup (R;\!R) \cup \cdots \cup (R;^{(n)}\!R) $$ where $;^{(n)}$ means that the total number of $R$'s is $n$ (e.g. $R;^{(3)}\!R = R;\!R;\!R$). This can be proven by induction and use of the distributive property in your link.
Assume $(a,b)\in R^{k}$. If $(a,b)\in (R;^{(i)}\!R)$ for any $i<k$, then $(a,b)\in R^{k-1}$ and we are done. Assume therefore that $(a,b)\in R;^{(k)}\!R$. That means there exist $s_1,\ldots,s_{k-1}\in S$ such that $$ (a,s_1), (s_1,s_2), \ldots, (s_{k-1},b) \in R $$ Lets rename $a=s_0$, $b=s_k$. There are $k+1$ $s_i$'s, so they cannot all be distinct. Say $s_i=s_j$ for some $i<j$. Then we have another chain of length $k-(j-i)$: $$ (s_0,s_1), \ldots (s_{i-1},s_i), (s_j, s_{j+1}), \ldots (s_{k-1},s_k) \in R $$ But that means that $$ (a,b)=(s_0,s_k) \in R;^{(k-j+i)}\!R \subset R^{k-1} $$ since $k-j+i\le k-1$. Therefore $R^k \subset R^{k-1}$, so indeed $R^k =R^{k-1}$.