15.2.17

I Can Do Proofs

In my last entry I made a typo when describing a sequence using two different formulas.

The first formula is 2i + (2i-1 - 3) if i is even or 2i + (2i-1 + 3) if i is odd for all i > 2
The second formula is 3*(2i-1 - 1) if i is even or 3*(2i-1 + 1) if i is odd for all i > 2

I claim that these two formulas are equivalent.

It may look counterintuitive that if i is even then 2i + (2i-1 - 3) = 3*(2i-1 - 1) and that if i is odd then 2i + (2i-1 + 3) = 3*(2i-1 + 1) but I can actually prove it.

Below I provide a proof using mathematical induction to show off my mad skillz.

Claim: For all i > 2, if i is even then 2i + (2i-1 - 3) = 3*(2i-1 - 1) and if i is odd then 2i + (2i-1 + 3) = 3*(2i-1 + 1).

Proof by weak mathematical induction:

Base Case: i = 3

 23 + (23-1 + 3) = 8 + (4 + 3) = 15
 3*(23-1 + 1) = 3*(4+1) = 15            Clearly, base case holds

Inductive Step:

Suppose that 2i + (2i-1 + 3) = 3*(2i-1 + 1) is true for an odd i, must show that the claim is also true for the next odd i, namely i + 2.

Since 2i + (2i-1 + 3) = 3*(2i-1 + 1) then 2i  3*(2i-1 + 1) - (2i-1 + 3) 

Replacing i with i+2 yields

2i + 2 = 3*(2i +2 - 1 +  1) - ( 2i + 2 - 1 + 3)
2i + 2 = 3*2i+1  + 3 -  2i+1  - 3
2i + 2 = 3*2i+1  + 0 -  2i+1
2i + 2 = 2*2i+1   = 2i + 2

Similarly, suppose that 2i + (2i-1 - 3) = 3*(2i-1 - 1) is true for an even i, must show that the claim is also true for the next even i, namely i + 2

Replacing i with i+2 yields

2i + 2 = 3*(2i +2 - 1 -  1) - ( 2i + 2 - 1 - 3)
2i + 2 = 3*2i+1  - 3 -  2i+1  + 3                  
2i + 2 = 3*2i+1  - 0 -  2i+1
2i + 2 = 2*2i+1   = 2i + 2
.'.