Results 1 to 5 of 5

Thread: Mathematical Induction

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    7

    Mathematical Induction

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

    Proof:
    Basis step:
    n = 1

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

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


    • $\displaystyle 5^(n+1) - 4(n+1) - 1 = 5^n+1 - 4n + 4 - 1$
    • $\displaystyle = 5^n+1 - 4n +3$
    • $\displaystyle =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

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

    and so we can find out what $\displaystyle 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): $\displaystyle 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 $\displaystyle 5^n-4n-1$ for all integers n greater than or equal to 1.

    Proof:
    Basis step:
    n = 1

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

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

    Multiply through by 5

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

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

    Move $\displaystyle -16n$ to RHS

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


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

    Since $\displaystyle 2n+5x $is an integer, $\displaystyle 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: Jun 29th 2010, 12:10 PM
  2. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Apr 7th 2010, 12:22 PM
  3. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: Jul 8th 2009, 12:27 AM
  4. Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Feb 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