If I have a recursively defined language L, for example:
How do I go about proving that every string which is in the set of strings {0, 1} with an even number of 1s is in L?
On
Proof by infinite descent: Let $M$ be the set of strings that have an even number of $1$s but that are not in $L$. Let $n > 0$ be the length of the shortest string in $M$. Any string in $M$ that is not in $L$ can made into a shorter string in $M$ either by removing the initial $0$, or by removing the initial $1$ and any other $1$. Applied to a string of length $n$, this procedure gives a string of length $n-1$ or $n-2$ that is also in $M$, contradiction.
A string $s$ with an even number of ones can have a prefix of a digit zero: $s=0p$.
Thanks to the rule 2, $(s\in L) \Leftarrow(p\in L)$, hence you can drop any leading zeros from a string and test the remaining part.
Then you have a string $p$ with an even number of ones and no leading zeros. So either $p$ is empty or it starts with $1$. If it's empty you're done (the empty string belongs to $L$ by the first rule).
Otherwise, let $m$ be a part between the first and the last one, and $n$ be the part (possibly empty) following the last one: $$p=1m1n$$ By the rule 3, $p\in L$ if both $m$ and $n$ belong to $L$.
However, as the second chosen one was the last one in $p$, the string $n$ must be empty or contain zeros only. An empty string belongs to the language by the rule 1, and zeros-only string can be reduced (as before) to an empty string by rule 2, hence $n\in L$.
The only remaining test is whether $m\in L$. But $m$ is a part of $p$ with two extreme ones (and possibly some zeros) dropped, so the same reasoning applies recursively.
Eventually we get to a base case of an empty string, or a zeros-only string, which can be reduced to an empty string, which is in $L$ — hence all preceding strings are in $L$, too, including the starting string $s$.