I have to prove that the language $L=\{a^ib^j:2i=3j+1\}$ and the CFG G with the following rewrite rules:
$S\rightarrow a^2Tb$
$T\rightarrow a^3Tb^2 |\epsilon$
are equivalent to each other.
I'm going to prove this by saying $L(G)\subseteq L$ and $L \subseteq L(G)$. I was able to prove the first one. I should be able to prove the second one with induction on the length on a word $w$. But how can I do that? The induction basis should start at length 3, because the smallest word $w \in L$ is $aab$. But the second word has a length of 8. This means the stepsize in the induction proof is 5. I've never done an inductive proof with a stepsize different from 1. How can I do something like this as it's not possible to state in the induction step that "We assume that the theorem holds for $|w|=n$, now we are going to proof that it holds for $|w|=n+5$"?
UPDATE: I think I found a solution to my own question:
Inductionbasis: Suppose $|w|=3$. Then $w$ must be $aab$ because that's the only word of length 3 that satisfies the requirements for the language L. But $aab$ is also an element of $L(G)$. The basis is OK.
Induction hypothesis: Assume that the theorem holds for all words $w`$ with length $|w`|=3+5n$. We are now going to proof that the theorem also holds for all words $w$ with length $|w|=3+5(n+1)$.
$w$ must be of the form $\alpha a^3b^2 \beta$ to be an element of $L$. Now consider the word $z=\alpha \beta$ with length $|z|=3+5n$. Then, by induction, we know that $z \in L \implies z \in L(G)$. Because $z \in L(G)$ it must hold that $z$ is of the form $a^nb^m$ with $2n=3m+1$. If we add the 3 $a$'s and 2 $b$'s from $w$ to this equation, we find that $2(n+3)=3(m+2)+1$. The following applies to this equation:
$2(n+3)=3(m+2)+1$
$\iff 2n+6=3m+6+1$
$\iff 2n+6=3m+1+6$
$\iff 2n+6=2n+6$
Thus, $w$ also satisfies $L(G)$. QED
Is this proof correct?