Tree or three
- My girl friend grew the tree above the other day.
- Is it really a tree?
- May be I misunderstood.
- That has happened to me too.
- She said that 2n – (-1)n is divisible by three and always odd.
- That is odd, my girl friend never talks to me like that.
November 25th, 2009 at 12:18 am
If n=0, 2^n – (-1)^n = 1 – 1 = 0, which is certainly divisible by 3, but it’s even. So let’s assume n is at least 1.
Theorem: 2^n – (-1)^n is divisible by three and always odd, if n is a positive integer.
Proof. Part 1: proving oddness.
2^n is even, and (-1)^n is odd, so 2^n – (-1)^n is odd.
Part 2: proving divisibility by 3.
If n=1, 2^n – (-1)^n = 2 – -1 = 3.
If n=2, 2^n – (-1)^n = 4 – 1 = 3.
Suppose (for a proof by induction) that the theorem is true for n-2.
Working modulo 3,
2^n – (-1)^n = 4 * 2^(n-2) – (-1)^(n-2)
= 2^(n-2) – (-1)^(n-2) (subtracting a multiple of 3)
= 0 (inductive hypothesis)
as required.