I would like to dedicate this post to the Redditor AlanCrowe. When I claimed that working out the formula using power series wouldn’t be that big of a deal, he said that this was “a rash thing to do” and that I would “end up summoning Cthulhu doing weird shit like that.”
How could I resist such a dare? The following manipulations contain no real mysteries; they are all direct applications of the binomial theorem and the distributive law. There is a small but transparent trick using complex numbers, which can be eliminated at the expense of more combinatorial footwork.
Disclaimer: Be careful working with power series. Power series may carry high voltages. Improper handling of power series may result in extreme divergence or serious mental anguish. Power series have no remorse. Do not taunt power series. If the double summations make you queasy, go for a short walk outside. I’ll wait.
UPDATE: notfancy has accused me of being a “cheater” for my use of complex numbers, claiming that I am relying on an implicit call to
De Moivre’s theorem Euler’s formula. I have seen this view elsewhere as well, that the use of tricks like this is tantamount to pulling a rabbit out of a hat.
I have a somewhat different viewpoint. At the heart of the series for and is the periodic sequence . And surely the mathematical techniques for manipulating this series can be no simpler than the series itself! In other words, I feel that my observation that we can write this sequence as was just notational convenience and nothing more. My own style is to prefer algebra to case analysis because I tend to make more mistakes in the latter.
To illustrate this, I am presenting the same proof, without an appeal to complex numbers. It requires a little more thought, but is overall a much simpler-looking approach.
First, for the purpose of notation, we need to make an observation about power series. If and , then . Nothing special here; just the distributive law. (if you are interested in going deeper into these kinds of manipulations of sequences, I highly recommend Wilf’s generatingfunctionology, available for free online)
In the same notation, if and , then and are the sequences and respectively.
Steps 1 and 2:
where , and
We have and , so . All that remains to be shown is that for all .
First, suppose that is odd. Then for all , so .
Now, suppose that is even. Then and . Hence .