Results 1 to 4 of 4

Math Help - Proof by Induction - Divisibility Proofs

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    140

    Proof by Induction - Divisibility Proofs

    Q. Prove by induction that...

    Please see attachment.

    The end result should be divisible by 6, but it hasn't worked out that way for me. Can someone help me spot where I've gone wrong? Thanks.
    Attached Thumbnails Attached Thumbnails Proof by Induction - Divisibility Proofs-photo-2-.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor ebaines's Avatar
    Joined
    Jun 2008
    From
    Illinois
    Posts
    1,043
    Thanks
    285

    Re: Proof by Induction - Divisibility Proofs

    Your error is in saying that  7^{k+1} + 4^{k+1} + 1 = 7 +4(6Z-1) That's incorrect. Try this:

     7^{k+1} + 4^{k+1} + 1 = 7(7^k + 4^k + 1) -3 \cdot 4^k -6

    Note that  3 \cdot 4^k -6 is divisible by 6. So if 7^{k+1} + 4^{k+1} + 1 is divisible by 6, then then so is  7^{k+1} + 4^{k+1} + 1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Proof by Induction - Divisibility Proofs

    Thanks, I really appreciate it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,682
    Thanks
    614

    Re: Proof by Induction - Divisibility Proofs

    Hello, GrigOrig99!

    \text{Prove by induction: }\:7^n + 4^n + 1\,\text{ is divisible by 6 for }n \in N.

    I prefer to do it like this . . .


    Verify S(1)\!:\;\;7^1 + 4^1 + 1 \,=\,12\:\hdots \text{ divisible by 6}


    Assume S(k)\!:\;\;7^k + 4^k + 1 \:=\:6m\,\text{ for some integer }m.


    Add 6\!\cdot\!7^k + 3\!\cdot\!4^k to both sides:

    - - . . 7^k + 4^k + 1 + 6\!\cdot\!7^k + 3\!\cdot\!4^k \;=\;6m + 6\!\cdot\!7^k + 3\!\cdot\!4^k

    . . (7^k + 6\!\cdot\!7^k) + (4^k + 3\!\cdot\!4^k) + 1 \;=\;6m + 6\!\cdot7^k + 3\!\cdot\!(2^2)^k

    - - - . 7^k(6+1) + 4^k(3+1) + 1\;=\;6m + 6\!\cdot\!7^k + 3\!\cdot\!2^{2k}

    . . . . . . . . . . . 7^k\!\cdot\!7 + 4^k\!\cdot\!4 + 1 \;=\;6m +6\!\cdot\!7^k + 3\!\cdot\!2\!\cdot\!2^{2k-1}

    . . . . . . . . . . . 7^{k+1} + 4^{k+1} + 1 \;=\;6m + 6\!\cdot\!7^k + 6\!\cdot\!2^{2k-1}

    . . . . . . . . . . . 7^{k+1} + 4^{k+1} + 1 \;=\;6\bigg[m + 7^k + 2^{2k-1}\bigg]


    And we have proved S(k+1).

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction - Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: September 26th 2011, 03:51 AM
  2. Induction Proof - Divisibility
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: February 5th 2011, 08:32 PM
  3. Proof by Induction (Divisibility)
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 8th 2010, 01:30 PM
  4. Replies: 1
    Last Post: October 11th 2009, 02:32 PM
  5. [SOLVED] Proof of divisibility by Induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 14th 2007, 08:15 PM

Search Tags


/mathhelpforum @mathhelpforum