Problem: (Stanford Putnam Practice) A finite sequence is called -balanced if any sum of the form is the same for . Prove that if a sequence with members is -balanced for , then all its members are equal to zero.
Solution: Let . Recall the strategy of isolating certain terms in a polynomial. Denoting by the th root of unity, we have
because all of the terms will cancel out by the identity except for the terms in which the power of the exponent is divisible by , in which case . Similarly, using the polynomials we obtain
from and . Hence we have a system of equations in the variables
But if we have a system of equations for , we have a total of equations. Since the only repeated value in the polynomial was and it showed up times, once for each prime, there are distinct points on the polynomial that we now know. However, since a polynomial of degree is defined by at most points, it must be the zero polynomial, which means , as desired. QED.
Comment: This is an example of generating functions showing up when you least expect it, well not exactly, but it was cool anyway. The proof above is not completely rigorous because we would need to show that a polynomial of degree actually cannot pass through all of the points, but it’s almost there.
Practice Problem: Let denote the number of ways you can partition into parts. Show that
Also show that the number of ways can be partitioned into unequal parts is equal to the number of ways can be partitioned into odd parts.
Leave a Reply
You must be logged in to post a comment.