Thread: Induction problem

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

Also, I am confused whether $\displaystyle (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!

Originally Posted by rednest

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

Hello Rednest

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

Check trivial values first.

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

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

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

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

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

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

Therefore by induction $\displaystyle f(n)$ is divisible by $\displaystyle 3$ for all $\displaystyle 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.

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

Prove n=1 is true:

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

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

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

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

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

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

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

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

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

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

Hello,

Originally Posted by rednest

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

Why do you wonder ?

Yes, it's correct :

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

And the rest follows

Originally Posted by bobak

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

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

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

Originally Posted by Air

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

Also $\displaystyle (2^3 -1) = 7$ then why did you write $\displaystyle 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

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

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.