** Claim: **

* 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.

I’m not quite understanding the rearranging step – could you please elaborate?

I got lost too, but it’s great besides that.

Amazing! Thank you again!

Sure, no problem. Feel free to ask questions on other posts if things aren’t clear.

Whow! That was fast!

Hi! Could you tell me how did you come up with the general law? Thanks

Sure, let me update the post (I’ll update it in the next 15-20 minutes) with an explanation for how you might come up with formula since other people might be curious also. Although, a lot of times in cases like this the easiest thing is to just write down the first few terms, guess the formula, and then prove your guess is right. It can be much easier to prove a formula you have is correct than to actually come up with the formula in the first place.

There, added an explanation for how to arrive at that formula. Hope that helps!