Respuesta :
As for every proof by induction, we start with the base case: the string '0' consists of an odd number of 0's and an even number of 1's, because there is one 0 and there are no 1s (and zero is even).
Now, if we let n represent the number of iterations, we have that the initial string '0' is the 0-th iteration. So, P(n) is the claim "the string built with the n-th iteration consist of an odd number of 0's and an even number of 1's", and we have just proven P(0).
Once the base case is proven, we can assume that all proposition from P(0) to P(n-1) are true.
We can build the n-th iteration in two ways:
CASE 1: The n-th iteration is in the form 1s1.
Since s is a string obtained at some previous iteration, we can assume that is consists of an odd number of 0's (say [tex]s_0[/tex]) and an even number of 1's (say [tex]s_1[/tex]). The string '1s1' has the following numbers of zeroes and ones:
- Zeroes: [tex]s_0[/tex]
- Ones: [tex]s_1+2[/tex]
In fact, starting from s, we only added two 1's (at the beginning and the end). So, '1s1' also has an odd number of 0's (because [tex]s_0[/tex] is odd) and an even number of 1's (because [tex]s_1+2[/tex] is the sum of two even numbers).
CASE 2: The n-th iteration is in the form s0t.
Since s and t are strings obtained at some previous iteration, we can assume that they consist of an odd number of 0's ([tex]say s_0,\ t_0[/tex]) and an even number of 1's (say [tex]s_1,\ t_1[/tex]).
Now, how many 0's and 1's are there in the string 's0t'?
- Zeroes: [tex]s_0+t_0+1[/tex]
- Ones: [tex]s_1+t_1[/tex]
In fact, starting from s and t, we only added one 0 (between the two original strings). So, 's0t' also has an odd number of 0's (because [tex]s_0+t_0+1[/tex] is the sum of three odd numbers, and thus odd) and an even number of 1's (because [tex]s_1+t_1[/tex] is the sum of two even numbers, and thus even).
