Mathematical proofs can often seem like magic tricks, because the authors do not explain how they discovered the ideas that led to their solutions. We endeavor to guide the reader along the shortest path from Point A to Point B, but sometimes it is better to take the scenic route.
The great mathematician Carl Gauss was known for writing clever solutions that concealed the original method of solution. His contemporary, Niels Abel, said of Gauss that “He is like the fox, who effaces his tracks in the sand with his tail.”
In my previous post, I pulled a rabbit out of a hat. I solved a recurrence by “guessing” the solution and plugging it in. In this post, I will explain how the solution could be discovered without guessing, and then I will reveal how I actually solved it.