While tutoring today a student asked me about the following identity
One way to prove it is to count the number of possible triples of sets with . This can be done in two ways. First, if contain elements respectively then the number of such triples clearly equals the left-hand side of . On the other hand, since each element of must belong to one of the four disjoint regions in the picture below
the number of such triples equals precisely .
An algebraic proof can be obtained by repeated use of the binomial theorem:
Similarly, one obtains the more general identity
This also follows from the multinomial theorem since the left-hand side equals
I recently found the following inequalities useful:
for any .
To prove the left half simply apply AM-GM to the product
The right half follows directly from Hölder’s inequality.
More generally, one has
for . The proof goes similarly.
One obtains similar inequalities for any number of vectors .
As an example, for we get the inequalities
using the fact that from above.
Let have order modulo . Then the base expansion of has period of length . To see this, note that if , then
Note also that for any . Hence has period . Now suppose that is even. Since has order modulo , it follows that . Hence . This means that at their midpoints the two numbers and are mirror images of one another. This means that splitting midway into two equal parts and adding them gives , i.e., a string of ‘s in base . This is known as Midy’s theorem.
For example, with and we get , and . Split into two equal parts and , adding which gives
In general, if is any divisor of , then
and so splitting into equal parts and adding them will always give a multiple of .