Results 1 to 5 of 5

Math Help - Proof by Induction

  1. #1
    Member
    Joined
    Jul 2007
    Posts
    147

    Proof by Induction

    In my book there is a following example:

    Prove by induction that 3 is a factor of  4^n-1

    the example has one step which baffles(in addition to the fact that I´m already baffled by induction as it is)
    <br />
4^{k+1} -1=4(4^k)-1
    =  4(4^k-1+1)-1 (why do you first subtract 1 and then add 1? Is this the mathematician´s creativity?)
     =4(4^k-1)+4(1)-1 (what happens here?)


    I´m a bit worried about this induction thing, because I´ve been trying to solve the homework problems for three days with very little progress. If anyone could help me with this problem I would be really grateful.

    One more thing, does anyone know any good book which would have mathematical induction for dummies?



    All help is appreciated very much.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    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 Coach View Post
    In my book there is a following example:

    Prove by induction that 3 is a factor of  4^n-1

    the example has one step which baffles(in addition to the fact that I´m already baffled by induction as it is)
    <br />
4^{k+1} -1=4(4^k)-1
    =  4(4^k-1+1)-1 (why do you first subtract 1 and then add 1? Is this the mathematician´s creativity?)
     =4(4^k-1)+4(1)-1 (what happens here?)
    Don't forget the first case, that is for n=1

    Now, the step. You gotta write the inductive hypothesis, in order to have it in mind. Because there's a probability of 99.9% that you'll use it.

    We want to prove that if 4^k-1 is a multiple of 3, then 4^{k+1}-1 is one too.

    So we start from 4^{k+1}-1
    As it is written, it's equal to 4(4^k)-1

    Now, you know that 4^k \quad \textbf{-1} is a multiple of 3. It's time to use it here. So let's write 4^k=4^k \quad \underbrace{\textbf{-1}+1}_{=0}
    By expanding, we get : 4(4^k-1)+4(1)-1=4(4^k-1)+3

    3 is obviously a multiple of 3 and 4^k-1 is a multiple of 3, according to the inductive hypothesis. The induction is proved.


    Another way of doing it is to assume that 4^k-1=3k, k an integer. And thus 4^k=3k+1

    Then 4^{k+1}-1=4(4^k)-1=4(3k+1)-1=4*3k+4-1=3(4k+1) \quad \blacksquare
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    4^{k + 1}  - 1 = 4^{k + 1}  - 4 + 4 - 1 = 4\left( {4^k  - 1} \right) + 3<br />
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Quote Originally Posted by Coach View Post
    =  4(4^k-1+1)-1 (why do you first subtract 1 and then add 1? Is this the mathematician´s creativity?)
    Pretty much. You want to somehow use the fact that 4^{k} - 1 is a multiple of 3. By looking at 4(4^{k}) - 1, we have the 4^{k} but what about the -1? So subtracting and adding 1 will take care of that and it just so happens that the rest of the expression turns out to be a multiple of 3.

    Don't worry about not being able to get these induction proofs. Some of them do require creativity but if you just go through as many examples as possible, you will catch on to a couple of tricks such as 'adding 0' as we did above and will hopefully be able to apply them when the exam comes around.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2007
    Posts
    147
    Thank you so much everyone!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum