Prove by Mathematical Induction

**princemac** · June 1st 2007, 09:23 AM

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.

**Jhevon** · June 1st 2007, 10:10 AM

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

**princemac** · June 1st 2007, 10:32 AM

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.

**earboth** · June 1st 2007, 10:33 AM

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}}$

**Jhevon** · June 1st 2007, 10:38 AM

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

**CaptainBlack** · June 1st 2007, 01:01 PM

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

**Plato** · June 1st 2007, 01:15 PM

Originally Posted by Jhevon

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

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.

**Soroban** · June 1st 2007, 03:18 PM

Hello, princemac!

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.

**Plato** · June 1st 2007, 03:50 PM

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?

**Soroban** · June 1st 2007, 04:54 PM

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).

**Plato** · June 1st 2007, 06:16 PM

Thank you for that.

Thread: Prove by Mathematical Induction

LinkBack

Thread Tools

Display

Prove by Mathematical Induction

Similar Math Help Forum Discussions

Rigorously prove the principle of complete induction from mathematical induction??

Prove By Mathematical Induction

using mathematical induction to prove..

using mathematical induction to prove something

Prove by Mathematical Induction

Search Tags