# 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:

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

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

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

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

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

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.