Proof. If , we have on the left, and on the right we have . Thus, the formula is true for .
Assume then that the formula is true for some . Then,
Thus, if the formula is true for then it is true for . Since we have established that it is true for , we then have that it is true for all
Update: From a request in the comments, we’ll add in a way to arrive at the formula (without just guessing).
First, we write,
Then, we consider the product
Where in the last line we cancelled terms again. The only things we are left with are the in the numerator and the 2 and in the denominator. Of course, this is pretty much a proof that the formula is correct without using induction, but it doesn’t rely on us guessing the formula correctly.
As noted in the comments, often it is easier to guess the correct formula and use induction to prove the formula is correct than to derive the formula directly.