Induction problem

**rednest** · May 30th 2008, 07:25 AM

For $n \in \mathbb{Z}^+$ , prove that $2^{3n+2} + 5^{n+1}$ is divisible by $3$ . (Proof by induction)

Also, I am confused whether $(2^5-2^2).2^{3n} = 2^{3n+2}(2^3-1)$ is correct or not. Please help! I am STUCK on induction, and my exams are in two weeks.

Any other advice on solving induction questions would be great.
Cheers!

**bobak** · May 30th 2008, 07:59 AM

Originally Posted by rednest

For $n \in \mathbb{Z}^+$ , prove that $2^{3n+2} + 5^{n+1}$ is divisible by $3$

Hello Rednest

Define $f(n) = 2^{3n+2} + 5^{n+1}$

Check trivial values first.

$f(0) = 2^2 + 5 = 9 = 3 \cdot 3$ It works.
$f(1) = 2^5 + 5^2 = 57 = 3 \cdot 19$ works for 1 as well

Now assume that $f(n)$ is divisible by 3 for all integer vaule of $n$ upto a particular value $k$

I see you attempted to evaluate $f(k+1) -f(k)$

$f(k+1) - f(k) =2^{3k+5} + 5^{k+2} - 2^{3k+2} - 5^{k+1}$

$\Rightarrow 2^{3k+2}(2^3 -1) + 5^{k+1}(5-1)$
$\Rightarrow 2^{3k+2}(7) + 5^{k+1}(4)$
$\Rightarrow 6 \cdot 2^{3k+2} + 3 \cdot 5^{k+1} + \underbrace{2^{3k+2} + 5^{k+1}}_{this\; is\; a\; multiple\; of\; 3 }$
$\therefore f(k+1) - f(k) = 3p$
$\therefore f(k+1) = 3p + f(k)$

So if $f(k)$ is divisible by 3 so i $f(k+1)$ as $f(0)$ and $f(1)$ are divisible by 3 then so is $f(2) , f(3)$ ad infinitum.

Therefore by induction $f(n)$ is divisible by $3$ for all $n \in \mathbb{Z}^+$ .

Bobak

Edit: I fixed my solution it is correct now. But this isn't the best method. Galactus post is more useful.

**galactus** · May 30th 2008, 09:21 AM

I worked this out, so I'll go ahead and post even though Bobak beat me.

Prove n=1 is true:

$2^{5}+5^{2}=57: \frac{57}{3}=19..........\text{true}$

Assume $2^{3k+2}+5^{k+1}=3p$ for some integer p.

If 3p is true, then so is $2^{3k+5}+5^{k+2}$

Add and subtract $3\cdot{2^{3k+2}}$ :

$8\cdot{2^{3k+2}}+5\cdot{5^{k+1}}+3\cdot{2^{3k+2}}-3\cdot{2^{3k+2}}$

$5\cdot{2^{3k+2}}+5\cdot{5^{k+1}}-3\cdot{2^{3k+2}}$

$5(\underbrace{2^{2k+2}+5^{k+1}}_{\text{3p}})-3\cdot{2^{3k+2}}$

$5(3p)-3\cdot{2^{3k+2}}$

$3(5p)-3(2^{3k+2})$

$3(5p-2^{3k+2})$ ...a multiple of 3.

**Moo** · May 30th 2008, 10:05 AM

Hello,

Originally Posted by rednest

Also, I am confused whether $(2^5-2^2).2^{3n} = 2^{3n+2}(2^3-1)$ is correct or not.

Why do you wonder ?

Yes, it's correct :

$2^5-2^2=2^2 \cdot 2^3-2^2 \cdot 1=2^2(2^3-1)$

And the rest follows

**Simplicity** · Jun 19th 2008, 02:18 AM

Originally Posted by bobak

$\Rightarrow 2^{3k+2}(2^3 -1) + 5^{k-2}(5^4-5^2)$
$\Rightarrow 2^{3k+2}(6) + 5^{k-2}(600)$
$f(k+1) = f(k) + 3( 2^{3k+3} + 8 \cdot 5^{k})$

Why did you choose to factorise out $5^{k-2}$ and not $5^{k+1}$ ?

Also $(2^3 -1) = 7$ then why did you write $6$ ?

**rednest** · Jun 19th 2008, 03:25 AM

Originally Posted by Air

Why did you choose to factorise out $5^{k-2}$ and not $5^{k+1}$ ?

Also $(2^3 -1) = 7$ then why did you write $6$ ?

Good point. I think he's made a mistake there, but I've sorted this problem out a long time ago anyway.

PS: Are you taking Edexcel FP3 exam by a chance? Just wondering

**bobak** · Jun 19th 2008, 04:28 AM

Sorry guys I fixed it now, Redness I believe Air is sitting FP3 (Future Pure Mathematics: Module Three) Tomorrow I'll be doing it as well, but do not discuss the exam on this forum after you sit it, other people will still be yet to sit the paper in other countires.

Bobak

**rednest** · Jun 19th 2008, 07:46 AM

Originally Posted by bobak

Sorry guys I fixed it now, Redness I believe Air is sitting FP3 (Future Pure Mathematics: Module Three) Tomorrow I'll be doing it as well, but do not discuss the exam on this forum after you sit it, other people will still be yet to sit the paper in other countires.

Bobak

Yeah the 12-hour rule. Anyways good luck to you all guys. I hope FP3 won't be as hard as FP2.

Thread: Induction problem

LinkBack

Thread Tools

Display

Induction problem

Similar Math Help Forum Discussions

Another induction problem help

Induction Problem

induction problem,

induction problem

Induction problem

Search Tags