Consider the following relation R on the set $W =\{0,1\}^{16}.$ For every two sequences $a = (a_1, \ldots,a_{16})$ and $b = (b_1,\ldots,b_{16})$ from $W$, we have $R(a,b)$ if and only if $b = (a_k,\ldots ,a_{16},a_1, \ldots,a_{k−1})$ for some $k \in \{1, \ldots,16\}$. (a) Prove that R is an equivalence relation.
This is what I have done so far:
Let $aRb$ such that there exists $a_k \in \{1,...,16\}, b =\{b_1,...,b_{16}\} = \{a_k,\ldots,a_{16},a_1,\ldots,a_{k-1}\}$
Let $bRc$ such that $k' \in \{1,...,16\}, c = \{c_1,\ldots,c_{16}\} = \{b_{k'},\ldots,b_{16},b_1,...b_{k'-1}\}$
Now i'm not sure how to write $c$ in terms of the sequence a to prove that $aRc$.
By definition $$aR b\iff \exists k\in[\![1,16]\!]\text{ such that }b=(a_k,\ldots,a_{16},a_1,\ldots,a_{k-1})$$ which means that $b$ is obtained from $a$ by shifting the first $k-1$ elements to the right. Then we have \begin{align*} b_j&=a_{(j+k-1)\ mod\ 16},\qquad \forall j\in[\![1,16]\!]\setminus\{\ 17-k\} \\ b_{17-k}&=a_{16} \end{align*} So to prove transitivity, let $a,b,c\in W$ such that $aR b$ and $bR c$, then $\exists k,s\in[\![1,16]\!]$ such that $$b_j=a_{(j+k-1)\ mod\ 16}\quad \text{and}\quad c_j=b_{(j+s-1)\ mod\ 16},\quad\forall j\in[\![1,16]\!]\setminus\{\ 17-k,17-s\}.$$ To prove $aRc$ we must write each $c_j$ in terms of coordinates of $a$ as the definition. We just replace in the two previous relations we obtain: \begin{align*} c_j&=b_{\color{blue}{\textrm{(j+s-1) $mod$ 16}}}\\ &=a_{\big(\color{blue}{\textrm{(j+s-1) $mod$ 16}}+k-1\big)mod\ 16}\\ &=a_{(j+s-1+k-1)mod\ 16}\\ &=a_{(j+m-1)mod\ 16} \end{align*} where $m:=(k+s-1)\mod 16$. In this way we get $c=(c_1,\ldots,c_{16})=(a_m,\ldots,a_{16},a_1,\ldots,a_{m-1})$, i.e, $aRc$ as desired. $ \qquad \qquad \square $
For example, we have $$c_1=a_{(1+m-1)\ mod\ 16}=a_{m\ mod\ 16}=a_m$$ $$c_{16}=a_{(16+m-1)\ mod\ 16}=a_{(m+15)\ mod\ 16}=a_{(m-1)\ mod\ 16}=a_{m-1}$$ Note we do the reduction modulo $16$ in indexation to ensure indexing stays in the interval $[\![1,16]\!]$.