Trick is induction step doesn't need to be base case $n = 8$ and the induction step from $k\to k+1$.
You can have base cases $n=8,9,10$ and induction step from $k \to k+3$. So the base case $n=8$ will give you $k=8,11,14,17.....$ and the base case $n=9$ will give you $k=9,12,15,18,....$ and base case $n=10$ will give you $k =10,13,16,19,.....$ and between the three base cases and the ability to induct from one case to the case three steps up... that's enough to conclude it's true for all.
Now to figure out the induction step: if $k = 3i + 5j$ then we can find $k+3 = ......$ Well, that's just too easy, isn't it?
.... alternative....
$1 = 2*3 - 1*5$ and $1 = 2*5 - 3*3$.
So if $k = 3*i + 5*j$ then $k+ 1 = 3(i+2) + 5(j-1)$ or $k+1 = 3(i-3) + 5(j+2)$.
If $j \ge 1$ we can do $k+1 = 3(i+2) + 5(j-1)$. If $i\ge 3$ we can do $k+1 =3(i-3) + 5(j+2)$.
So we can always go from $k\to k+1$ so long as either $j \ge 1$ or $i \ge 3$.
But what if $j \le 0$ and $i\le 2$? Well, then $n\le 3*2 + 5*0 = 6$. Which is not an issue if our base cases are $n = 8,9,10$.