# Thread: Prove by Mathematical Induction

1. ## 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.

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

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

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

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

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

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

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

9. 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?

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

11. Thank you for that.