Prove that Un = (2^n - (-1)^n)/3 is an odd number for all positive integers

M

Masaru

Junior Member
Joined
Sep 6, 2013
Messages
59
Although this is not a proper proof, I can explain it like this:

Odd number/Odd number = Odd
Even number/Odd number = Even

So the numerator 2^n - (-1)^n has to be an odd number.

Since 2^k is always an even number and (-1)^k gives always either +1 or -1, the result must be an odd number.

However, the above explanation does not prove that the numerator is always divisible by 3.

On top of that, this question is under "Mathematcial Induction" in a textbook, so we need to logically and mathematically prove it using "the principle of mathematical induction".

My incomplete working is as follows:

Pn (Proposition) is: Un = (2^n - (-1)^n)/3 = 2A + 1 for all n = 1, 2, 3..... and all A = 0, 1, 2, 3.....

1) If n = 1, U1 = (2^1 - (-1)^1)/3 = 3/3 = 1, which is an odd number where A = 0, so P1 is true.

2) If Pk is true, then Uk =
(2^k - (-1)^k)/3 = 2A + 1
for all k = 1, 2, 3..... and all A = 0, 1, 2, 3.....​
​

Now Uk+1 =
(2^(k+1) - (-1)^(k+1))/3 =​

And I cannot go further than this, with no idea how I can manipulate the expression for Uk+1 above using the expression for Uk to prove that the result is also an odd number.

I would much appreciate it if someone can help me with this question.

Thank you.
 
Masaru said:
Although this is not a proper proof, I can explain it like this:

Odd number/Odd number = Odd
Even number/Odd number = Even

So the numerator 2^n - (-1)^n has to be an odd number.

Since 2^k is always an even number and (-1)^k gives always either +1 or -1, the result must be an odd number.

However, the above explanation does not prove that the numerator is always divisible by 3.

On top of that, this question is under "Mathematcial Induction" in a textbook, so we need to logically and mathematically prove it using "the principle of mathematical induction".

My incomplete working is as follows:

Pn (Proposition) is: Un = (2^n - (-1)^n)/3 = 2A + 1 for all n = 1, 2, 3..... and all A = 0, 1, 2, 3.....

1) If n = 1, U1 = (2^1 - (-1)^1)/3 = 3/3 = 1, which is an odd number where A = 0, so P1 is true.

2) If Pk is true, then Uk =
(2^k - (-1)^k)/3 = 2A + 1
for all k = 1, 2, 3..... and all A = 0, 1, 2, 3.....​
​

Now Uk+1 =
(2^(k+1) - (-1)^(k+1))/3 =​

And I cannot go further than this, with no idea how I can manipulate the expression for Uk+1 above using the expression for Uk to prove that the result is also an odd number.

I would much appreciate it if someone can help me with this question.

Thank you.
Click to expand...
(2^(k+1) - (-1)^(k+1)) = 2 * 2^k + (-1)^k

(2^(k+1) - (-1)^(k+1)) + (2^k - (-1)^k) = 3 * 2^k ....... divisible by 3
 
You must log in or register to reply here.
Top