Results 1 to 5 of 5

Math Help - Mathematical Induction

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    7

    Mathematical Induction

    8 divides 5^n-4n-1 for all integers n greater than or equal to 1.

    Proof:
    Basis step:
    n = 1

    5^1-4(1)-1 = 0
    0/8 = 0
    8 divides 5^n-4n-1 if n=1

    Induction step:
    Assume 5^n-4n-1 is divisible by 8 (induction hypothesis)
    [show 5^(n+1) - 4(n+1) - 1 is divisible by 8]


    • 5^(n+1) - 4(n+1) - 1 = 5^n+1 - 4n + 4 - 1
    • = 5^n+1 - 4n +3
    • =5^n *5^1 - 4n +3

    ...now im not sure where to go
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Apr 2010
    Posts
    7
    ...sorry the first bullet should be 5^n+1 - 4(n+1) -1 = ....
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    7
    damn, and the second one should be 5^n+1 - 4n + 3
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    A few points.

    1. You can use the "Edit" feature rather than posting multiple times, it will keep the thread cleaner.

    2. You made a silly error of not distributing the -4 properly, so you should have -5 where you currently have +3.

    3. I think the problem can be solved by considering that when n is odd, 4n+1 is congruent to 5 (mod 8), and when n is even, 4n+1 is congruent to 1 (mod 8). That is, we have by induction hypothesis

    5^n-(4n+1)\equiv0\ (\text{mod}\ 8)

    and so we can find out what 5^n is (mod 8), by considering the two cases, n odd or even.

    4. The way to get exponents with more than one character in LaTeX is like this (hover mouse over it to see the code): x^{12345}.

    Edit: I had a typo; the -4 in red above used to say -1.
    Last edited by undefined; May 9th 2010 at 06:04 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by luckyNUM7 View Post
    8 divides 5^n-4n-1 for all integers n greater than or equal to 1.

    Proof:
    Basis step:
    n = 1

    5^1-4(1)-1 = 0
    0/8 = 0
    8 divides 5^n-4n-1 if n=1

    Induction step:
    Assume 5^n-4n-1 is divisible by 8 (induction hypothesis)
    [show 5^(n+1) - 4(n+1) - 1 is divisible by 8]
    Since 5^n-4n-1 is divisible by 8, then 5^n-4n-1=8x, x\in \mathbb{Z}

    Multiply through by 5

    5\cdot 5^n-5\cdot 4n-5\cdot 1=5\cdot 8x

    5^{n+1}-4n-16n-4-1=5\cdot 8x

    Move -16n to RHS

    5^{n+1}-(4n-4)-1=16n+5\cdot 8x


    5^{n+1}-4(n+1)-1=8(2n+5x)

    Since 2n+5x is an integer, 5^{n+1}-4(n+1)-1 is divisible by 8.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 7th 2010, 12:22 PM
  3. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: July 8th 2009, 12:27 AM
  4. Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 17th 2009, 11:30 AM
  5. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 30th 2007, 03:21 PM

Search Tags


/mathhelpforum @mathhelpforum