# Prove by Mathematical Induction

• Jun 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:

$\displaystyle 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 $\displaystyle 2^{n+2} + 3^{2n+1}$ is divisible by 7

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

where a is a positive integer

2) $\displaystyle P_1$ statement where n=1

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

Therefore $\displaystyle P_1$ is true.

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

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

4) Therefore

$\displaystyle 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 $\displaystyle P_{k+1}$ is divisible by 7.

Any help would be greately appreciated.
• Jun 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:

$\displaystyle 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 $\displaystyle 2^{n+2} + 3^{2n+1}$ is divisible by 7

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

where a is a positive integer

2) $\displaystyle P_1$ statement where n=1

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

Therefore $\displaystyle P_1$ is true.

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

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

4) Therefore

$\displaystyle 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 $\displaystyle 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.

$\displaystyle 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

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

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

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

which is divisible by 7
• Jun 1st 2007, 10:32 AM
princemac
Ahhh many thanks, now that Ive seen what you did I can see another way.

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

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

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

Thats pretty cool with the zero, I'll have to remeber that.
Thanks again.
• Jun 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:

$\displaystyle 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 $\displaystyle 2^{n+2} + 3^{2n+1}$ is divisible by 7

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

where a is a positive integer

2) $\displaystyle P_1$ statement where n=1

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

Therefore $\displaystyle P_1$ is true.

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

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

4) Therefore

$\displaystyle 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 $\displaystyle 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:

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

$\displaystyle \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}}$
• Jun 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
• Jun 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
• Jun 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.
• Jun 1st 2007, 03:18 PM
Soroban
Hello, princemac!

Quote:

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

Your work is correct . . .

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

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

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

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

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

. . $\displaystyle \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}$

- . - $\displaystyle 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}$

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

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

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

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

We have proved $\displaystyle P(k+1)$ . . . The inductive proof is complete.

• Jun 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?
• Jun 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).
• Jun 1st 2007, 06:16 PM
Plato
Thank you for that.