Well, the thing is, you did find $k$ -- it just didn't pop out named $k$, so to speak. Everything you know about $k$ will be just as true for $ij$ here, it just looks a little different (but only superficially).
From the presentation, you know that $ij$ is in the group being presented, because it is a group, and must be closed under the group operation.
As Matt Samuel said in the comments, presentations aren't always nice - and often they're pretty demanding, computationally. But, with sheer willpower, you can often wrestle such a presentation to learn more about your group. Here's the way I would approach it, but I make no claims of efficiency!
Disclaimer: Working with presentations is like an exercise in using algebraic identities dozens of times; I find such a thing impossibly hard to follow looking at someone else's work, but moderately fun to do once or twice a year. So, you'll probably want to follow along with a pencil and paper, if you actually want to digest any of this.
Since $i^4 = 1$, we must have that $\langle i \rangle = \{1, i, i^2, i^3\}$ is a cyclic subgroup. And, since $i^2 = j^2$, we can verify that $\langle j \rangle$ is another cyclic subgroup of size four. Except, in addition, we can clean up by using a few relations, to see that $\langle j \rangle = \{1, j, j^2, j^3\} = \{1, j, i^2, i^2j\}$.
So far, we've identified six unique elements: $1, i, j, i^2, i^3,$ and $i^2j$. But, we haven't learned much about $ij$, so we'll at least find its order now. Note that by the relation $j^{-1}ij = i^{-1}$, we know that $iji = j$ (right multiply by $i$, and left multiply by $j$). Now
$$(ij)^2 = \underbrace{iji}_j\cdot j = j^2 = i^2,$$
and by the same reasoning above, we know that $\langle ij \rangle = \{1, (ij), (ij)^2, (ij)^3\} = \{1, ij, i^2, i^3j\}$.
So now our list of elements contains
\begin{array}{cccc} 1 & i & i^2 & i^3 \\ j & ij & i^2j & i^3j \end{array} at least. Now, in order to show that we've found everything, we'll have to show that multiplication (on either side) by $i$ or $j$ gives us back something from this list. Of course, left multiplication by $i$, and right multiplication by $j$, will easily be seen to give us back something from the list.
In general, it would be nice to be able to put all of our products in the form $i^mj^n$, at which point we'll show that $m \in \{0, 1, 2, 3\}$ and $n \in \{0, 1\}$, and our list is indeed exhaustive. In order to arrive at this form, the commutator $[j, i] = j^{-1}i^{-1}ji$ will be extremely helpful, as $ij[j, i] = ji$. We'll see that $[j,i]$ will allow us to let the $i$'s and $j$'s switch places if we're willing to pay the commutator price. We'll see that here, $[j, i] = i^2 = j^2 = (ij)^2$. Try it yourself, what follows is one way.
Since $j^{-1}i^{-1} = (ij)^{-1} = i^3j$, we have
$$j^{-1}i^{-1}ji = i^3jji = i^3j^2i = i^3i^2i = i^2.$$
In practice, this is quite useful. Let's pick $i^2j$ from our list above, and right multiply by $i$, attempting to simplify $i^2ji$ to give it the form $i^mj^n$. Since we know that $ji = ij[j,i] = iji^2 = ijj^2 = ij^3$, we have
$$i^2ji = i^2(ij^3) = i^3j^3 = i^{-1}j^2j = i^{-1}i^2j = ij,$$ something from our list.
I'll spare you the rest (verifying the list is truly exhaustive), because it's really more enlightening just to dig in and see what you can figure out. But hopefully it will give you more of an idea how such a thing can work, in practice. You could take it a step further and construct the multiplication table, or verify all the things you know about $Q_8$, using the element list here.
For some groups, presentations are really nice; you can basically collapse the multiplication table of the dihedral groups into a $2 \times 2$ table (reflections and rotations), using presentations.
Here's a little elaboration: Any element of the group $G$ given by the presentation above may be thought of as a word, that is, a finite sequence in $r$ and $s$ and their inverses.
Notice, the relation $rs = sr^{-1}$ allows us to progressively rearrange our words so that they are of the form $s^kr^{\ell}$. For example, $$\begin{align}rsr^2s^{-3}r &\leadsto sr^{-1}r^2s^{-3}r^4 = srs^{-3}r^4 \\ &\leadsto r^{-1}s^{-2}r^4 \\ &\leadsto\dots\\ &\leadsto s^{-2}r^3.\end{align}$$ After we have reached this form, applying $r^n=1$ and $s^2=1$ repeatedly leads us to a uniquely determined word for each group element—this is called a normal form. Counting possibilities for the exponents of $r$ and $s$ leads to a total of $n\cdot 2 = 2n$ possible words (the normal form for the identity element is $s^0r^0$), thus yielding an upper bound on the size of any group satisfying these relations, i.e. $|G| \le 2n$.
The fact that there is a group of order $2n$ satisfying these relations, the dihedral group, tells us that the dihedral group has a presentation given by $G$.
In general, an argument just from a group presentation itself is much more likely to give you an upper bound on the order of the group than a lower bound, simply because it's rather tough to argue that, given a group presentation, a word cannot represent the identity. Indeed, there's a famous open conjecture about presentations of the trivial group!
Best Answer
The part you are asking about doesn't require induction. The trick is that $rs=sr^{-1} $ is an "anti-commutativity" relation, and allows you to switch the order of $r $ and $s$ (at a price, so to speak).
To take a very simple example, $srs=s(rs)=s (sr^{\color{blue}{-1}})=s^2r^{-1}=r^{n-1}$.
It's pretty clear that this sort of swapping will enable us to gather all the $s $'s and $r $'s together, so that everything can be written in the form $s^ar^b $.
Incidentally this immediately gives a bound on the size of the group.