Prove by Mathematical Induction

Printable View

June 1st 2007, 09:23 AM
princemac

Prove by Mathematical Induction

Hi everyone I need a little help, Im stuck.

I have to prove by induction that:

$ 2^{n+2} + 3^{2n+1} $

is exactly divisible by 7 for all positive integers of n.

Now what I have done is:

1)

If $2^{n+2} + 3^{2n+1}$ is divisible by 7

=>( $2^{n+2} + 3^{2n+1}=7a$ )-----> Pn statement

where a is a positive integer

2) $P_1$ statement where n=1

=>
LHS: $2^{1+2} + 3^{2(1)+1} = 35$
RHS: $7(5) = 35$

Therefore $P_1$ is true.

3) Assuming $P_k$ to be true where n=k

=> $P_k = 2^{k+2} + 3^{2k+1} = 7a$

4) Therefore

$P_{k+1} = 2^{(K+1)+2} + 3^{2(k+1)+1}$

Now here is where Im stuck, Im not getting to factor out a 7 i.e.
getting 7(some integer) to prove that $P_{k+1}$ is divisible by 7.

Any help would be greately appreciated.
June 1st 2007, 10:10 AM
Jhevon

Quote:

Originally Posted by princemac

Hi everyone I need a little help, Im stuck.

I have to prove by induction that:

$ 2^{n+2} + 3^{2n+1} $

is exactly divisible by 7 for all positive integers of n.

Now what I have done is:

1)

If $2^{n+2} + 3^{2n+1}$ is divisible by 7

=>( $2^{n+2} + 3^{2n+1}=7a$ )-----> Pn statement

where a is a positive integer

2) $P_1$ statement where n=1

=>
LHS: $2^{1+2} + 3^{2(1)+1} = 35$
RHS: $7(5) = 35$

Therefore $P_1$ is true.

3) Assuming $P_k$ to be true where n=k

=> $P_k = 2^{k+2} + 3^{2k+1} = 7a$

4) Therefore

$P_{k+1} = 2^{(K+1)+2} + 3^{2(k+1)+1}$

Now here is where Im stuck, Im not getting to factor out a 7 i.e.
getting 7(some integer) to prove that $P_{k+1}$ is divisible by 7.

Any help would be greately appreciated.

for (4), we will do a trick often used in math--add zero in a weird way, that way we don't change anything, but are able to factor things in a convenient way.

$P(k+1): 2^{k+3} + 3^{2k + 3} = 2^{k + 3} \underbrace { + 2 \cdot 3^{2k + 1} - 2 \cdot 3^{2k + 1} } + 3^{2k + 3}$

Note that what is underbraced is zero

$= 2 \left( 2^{k + 2} + 3^{2k + 1} \right) - 3^{2k + 1} \left( 2 - 3^2\right)$

$= 2 \cdot 7a + 7 \cdot 3^{2k + 1}$

$= 7 \left( 2a + 3^{2k + 1} \right)$

which is divisible by 7
June 1st 2007, 10:32 AM
princemac

Ahhh many thanks, now that Ive seen what you did I can see another way.

$P_{k+1}= 2^{k+3} + 3^{2k + 3} = (2)(2^{k+2}) + (9)3^{2k + 1} $

$2^{k+2}= 7a - 3^{2k + 1}$

Therefore
$P_{k+1} = 14a + 3^{2k + 1}(9 -2)= 7(2a +$ $3^{2k+1})$

Thats pretty cool with the zero, I'll have to remeber that.
Thanks again.
June 1st 2007, 10:33 AM
earboth

Quote:

Originally Posted by princemac

Hi everyone I need a little help, Im stuck.

I have to prove by induction that:

$ 2^{n+2} + 3^{2n+1} $

is exactly divisible by 7 for all positive integers of n.

Now what I have done is:

1)

If $2^{n+2} + 3^{2n+1}$ is divisible by 7

=>( $2^{n+2} + 3^{2n+1}=7a$ )-----> Pn statement

where a is a positive integer

2) $P_1$ statement where n=1

=>
LHS: $2^{1+2} + 3^{2(1)+1} = 35$
RHS: $7(5) = 35$

Therefore $P_1$ is true.

3) Assuming $P_k$ to be true where n=k

=> $P_k = 2^{k+2} + 3^{2k+1} = 7a$

4) Therefore

$P_{k+1} = 2^{(K+1)+2} + 3^{2(k+1)+1}$

Now here is where Im stuck, Im not getting to factor out a 7 i.e.
getting 7(some integer) to prove that $P_{k+1}$ is divisible by 7.

Any help would be greately appreciated.

Hello,

I take over your result and transform it a little bit:

$P_{k+1} = 2^{(K+1)+2} + 3^{2(k+1)+1} =$
$2 \cdot 2^{k+2} + 9 \cdot 3^{2k+1} =$
$2^{k+2} + 2^{k+2} + 3^{2k+1} + 3^{2k+1} + 7 \cdot 3^{2k+1}$ rearrange the summands:

$\underbrace{2^{k+2} + 3^{2k+1}}_{\text{divisible by 7}} + \underbrace{2^{k+2} + 3^{2k+1}}_{\text{divisible by 7}} + \underbrace{7 \cdot 3^{2k+1}}_{\text{divisible by 7}}$
June 1st 2007, 10:38 AM
Jhevon

once again, it seems i was thinking too hard. both your methods seem nicer than mine for some reason
June 1st 2007, 01:01 PM
CaptainBlack

Quote:

Originally Posted by Jhevon

once again, it seems i was thinking too hard. both your methods seem nicer than mine for some reason

Disagree, yours seems more elegant to me.

RonL
June 1st 2007, 01:15 PM
Plato

Quote:

Originally Posted by Jhevon

once again, it seems i was thinking too hard. both your methods seem nicer than mine for some reason

Quote:

Originally Posted by CaptainBlack

Disagree, yours seems more elegant to me.
RonL

I am with the Captain all the way on this one!
Jhevon, yours is the preferred way because it is easier to remember after one has done several of these.
June 1st 2007, 03:18 PM
Soroban

Hello, princemac!

Quote:

I have to prove by induction that:
$2^{n+2} + 3^{2n+1}$ is divisible by 7 for all positive integers $n$ .

Your work is correct . . .

Verify $P(1):\;\;2^{k+2} + 3^{2\cdot1+1} \:= \:35$ . . . True!

Assume $P(k)$ is true: . $2^{k+2} + 3^{2k+1} \:= \:7a$ .for some integer $a$ .

We want to prove $P(k+1):\;2^{k+3} + 3^{2k + 3} \:=\:7b$ .for some integer $b$ .
[I like to write this statement now, so I know what I'm aiming for.]

Begin with $P(k):\;2^{k+2} + 3^{2k+1} \:=\:7a$

Add $2^{k+2} + 8\!\cdot\!3^{2k+1}$ to both sides:

. . $\underbrace{2^{k+2} + 2^{k+2}} + \underbrace{3^{2k+1} + 8\!\cdot\!3^{2k+1}} \;=\;7a + 2^{k+2} + 8\!\cdot\!3^{2k+1}$

- . - $2\!\cdot\!2^{k+2} \quad+ \quad(1 + 8)\!\cdot\!3^{2k+1} \;= \;7a + \underbrace{2^{k+2} + 3^{2k+1}}_{\text{this is }7a} + 7\!\cdot\!3^{2k+1}$

. . . . . . . . . . $2^{k+3} \;+ \;9\!\cdot\!3^{2k+1} \;=\;7a + 7a + 7\!\cdot\!3^{2k+1}$

. - . . - . . . . . $2^{k+3} + 3^2\!\cdot\!3^{2k+1} \;=\;14a + 7\!\cdot\!3^{2k+1}$

. . . . . . . . . . . $2^{k+3} + 3^{2k+3} \;=\;7\underbrace{(2a + 3^{2k+1})}_{\text{This is an integer}}$

Therefore: . . . $2^{k+3} + 3^{2k+3} \;=\;7b$

We have proved $P(k+1)$ . . . The inductive proof is complete.
June 1st 2007, 03:50 PM
Plato

Is it a general rule that one should read the entire thread before responding?
If not, there ought to be such a rule!
Is the pervious post in this thread a case in my point?
June 1st 2007, 04:54 PM
Soroban

Absolutely right, Plato!

Guilty as charged . . .

I thought I read through the posts (evidently not)
. . and thought I had something original to offer (wrong again).
June 1st 2007, 06:16 PM
Plato

Thank you for that.