Thursday, March 14, 2019

Little math problem

For pi day here is a little mathematical proof problem for math geeks.

For every natural number n, 20 + 21 + ...+ 2n = 2n+1 − 1.

It's true for n = 1 to 5 as follows:
n=1: 20 + 21 = 3 = 22 − 1
n=2: 20 + 21 + 22 = 7 = 23 − 1
n=3: 20 + 21 + 22 + 23 = 15 = 24 − 1
n=4: 20 + 21 + 22 + 23 + 24 = 31 = 25 − 1
n=5: 20 + 21 + 22 + 23 + 24 + 25 = 63 = 26 − 1
The general formula for all n is proven by mathematical induction as follows and shown here.

Base case: Set n = 0. Then 20 = 1 = 21 − 1.
Induction step: Show that if the equation holds for any particular n, which the above does, 
it also holds for n+1.
Let n be any natural number and 20 + 21 + ... + 2n = 2n+1 − 1 is true.
Then 20 + 21 + ...+ 2n + 2n+1 = ( 20 + 21 + ... + 2n ) + 2n+1
                                               = ( 2n+1 - 1) + 2n+1
                                               = 2 * 2n+1 - 1
                                               = 2n+2 - 1. QED

There is another proof as well. I will post it this weekend to give readers some time to try to find it on their own.

+++++++++++

March 16. The other proof follows. 20 + 21 + ...+ 2n is a sum of a geometric progression. Using long division, the quotient of (xn+1 − 1)÷(x - 1) is xn + xn-1 + xn-2 +... 1 = xn + xn-1 + xn-2 +...+ x0.
Reverse the order of the sum and let x = 2:
20 + 21 + ... + 2n = (2n+1 − 1)÷(2 - 1) = 2n+1 − 1.

No comments:

Post a Comment