I want to prove by mathematical induction that the XOR-function is satisfied for any non-negative integer.
Here is the definition of the XOR-function.
Definition. [XOR function] Suppose that x is a string of binary bits (0s and 1s). If the number of 1s in the string x is odd, then the function XOR(x) = 1. Otherwise, if the number of 1's in the x is even, then XOR**(x**) = 0.
e.g. $$XOR(1010) = 1 \oplus 0 \oplus 1 \oplus 0 = 0$$ or another example $$XOR(11100)= 1 \oplus 1 \oplus 1 \oplus 0 \oplus 0 = 1$$.
In order to prove that the function XOR is satisified for any non-negative integer, I have two cases. That is, basis step and inductive step. I can show the basis step for XOR function. But, I cannot show the inductive step. Thus, can you show me an intuitive idea of how to show the inductive step of the XOR function?
First, you need to state clearly what you are trying to prove. You want to show that the XOR of all the elements of any bit string is $1$ if the number of $1$ bits in the string is odd and is $0$ if the number of $1$ bits in the string is even. Second, you follow the recipe for an inductive proof. Base case: strings of $1$ bit. $XOR(0)=0, XOR(1)=1$. We can see that the statement is satisfied. Now assume that the statement is true for all strings of length $k$. A string of length $k+1$ is either a string of length $k$ that has an even number of $1$'s with a $0$ appended or (3 more possibilities). In the first case, the string of length $k+1$ has an even number of $1$'s and the result is $XOR(0,0)=0$ Verify the other three cases and you are done.