Results 1 to 8 of 8

Math Help - Induction problem

  1. #1
    Junior Member rednest's Avatar
    Joined
    Mar 2008
    Posts
    36

    Wink Induction problem

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Oct 2007
    From
    London / Cambridge
    Posts
    591
    Quote Originally Posted by rednest View Post

    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.
    Last edited by bobak; June 19th 2008 at 04:23 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Quote Originally Posted by rednest View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Sep 2007
    Posts
    528
    Awards
    1
    Quote Originally Posted by bobak View Post

    \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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member rednest's Avatar
    Joined
    Mar 2008
    Posts
    36
    Quote Originally Posted by Air View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Oct 2007
    From
    London / Cambridge
    Posts
    591
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member rednest's Avatar
    Joined
    Mar 2008
    Posts
    36
    Quote Originally Posted by bobak View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Another induction problem help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 12th 2012, 04:57 PM
  2. Induction Problem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 26th 2010, 05:00 AM
  3. induction problem,
    Posted in the Calculus Forum
    Replies: 1
    Last Post: June 7th 2009, 05:57 AM
  4. induction problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 26th 2008, 12:04 PM
  5. Induction problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 16th 2008, 04:41 AM

Search Tags


/mathhelpforum @mathhelpforum