If $s \geq 3$, $3$ divides $s$, and $t = s/3$, then $t+1 < s$.

79 Views Asked by At

I am using the pumping lemma to prove a language is not regular, and would like to assert what I have stated in the title of the question to complete my proof. That is, if $s \geq 3$, $3$ divides $s$, and $t = s/3$, then $t+1 < s$. Could someone hint as to how I could prove this statement to in fact be true?

Below is a picture of proof at the moment; this statement is the final piece to the proof that will allow me to show $\hat{w}$ must be a string of only $\mathtt{a}$'s but at the same time it must include a $\mathtt{b}$ which is self contradictory and so such a string cannot exist.

enter image description here

3

There are 3 best solutions below

0
On BEST ANSWER

$$\begin{align}s-(t+1)&=s-(s/3)-1\\&=(2s/3)-1\\&\ge 2-1\\&=1\\&\gt0.\end{align}$$

0
On

working in $\mathbb Z$ here $s>0\wedge s=3t\Rightarrow t\geq 1$ so $s=3t=t+2t\geq t+2>t+1$.

0
On

By multiplying both sides with $3$, the inequality $t+1<s$ is equivalent with $s+3<3s$, or $3<2s$