Math Is Fun Forum

chetah

Member

Registered: 2008-02-15

Posts: 32

Discrete Math Proves

For all n E Z, n >= 0 prove that
(a.) 2^2n+1 + 1 is divisible by 3

(b.) n^3 +(n + 1)^3 + (n+2)^3 is divisible by 9

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Discrete Math Proves

These are both proofs by induction. First you prove the statement is true when n = 1, then you assume it's true for n = k and show that that means it's true for n = k+1. I'll do the first one.

a) Let p(n) be 2^(2n+1) + 1.
Then p(1) = 2^3 + 1 = 9, which is divisible by 3.

Now assume that p(k) is divisible by 3. So, 2^(2k+1) + 1 = 3t, for some integer t.
Consider p(k+1) = 2^(2(k+1)+1)) + 1.
This is 2^(2k+3) + 1
= 4 x 2^(2k+1) + 1
= (3+1) x 2^(2k+1) + 1
= 3 x 2^(2k+1) + 3t
= 3(2^(2k+1) + t)

Hence, p(k+1) is divisible by 3.
Then, by induction, p(n) is divisible by 3, for all n.

---

Why did the vector cross the road?
It wanted to be normal.

Kurre

Member

Registered: 2006-07-18

Posts: 280

Re: Discrete Math Proves

you dont need induction for the second one, just expand the paranthesis and simplify, and you will end up with an expression that you can easy show that it is divisible by 9 by letting n=3 and n=3k±1. (you can also first change n^3 +(n + 1)^3 + (n+2)^3 to (n - 1)^3 + n^3 + (n+1)^3, which may simplify the expansion)

chetah

Member

Registered: 2008-02-15

Posts: 32

Re: Discrete Math Proves

This is 2^(2k+3) + 1
= 4 x 2^(2k+1) + 1
= (3+1) x 2^(2k+1) + 1
= 3 x 2^(2k+1) + 3t
= 3(2^(2k+1) + t)

I am trying to understand the proove. Where does the 4 comes from?  How is it decomposed to get (3 + 1)?

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Discrete Math Proves

You add indices when mutliplying: