Results 1 to 6 of 6

Thread: Proof by induction

  1. #1
    Newbie
    Joined
    Oct 2007
    Posts
    17

    Proof by induction

    I need to prove 11^n - 6 is divisible by 5 for all n >or = to 1 by induction.
    So I start by basis step 11^1 -6 get 5 and 5 is divisible by 5 so basis step is true.

    Then I am suppose to add n +1 to both sides and show it is still true.

    I am stumped!!! Anyone willing to help a very old and confused student???!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    Awards
    1
    Here is the basic trick.
    $\displaystyle 11^{N + 1} - 6 = \left( {11^{N + 1} - 6 \cdot 11} \right) + \left( {6 \cdot 11 - 6} \right) = 11\left( {11^N - 6} \right) + \left( {6 \cdot 11 - 6} \right)$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2007
    Posts
    17
    Plato, Thank you for your time and effort on my last two threads. This subject is not like any other I have tackled and I really appreciate your assisitance!!!!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,152
    Thanks
    731
    Awards
    1
    Quote Originally Posted by frostking2 View Post
    I need to prove 11^n - 6 is divisible by 5 for all n >or = to 1 by induction.
    So I start by basis step 11^1 -6 get 5 and 5 is divisible by 5 so basis step is true.

    Then I am suppose to add n +1 to both sides and show it is still true.

    I am stumped!!! Anyone willing to help a very old and confused student???!!!
    Here's another way.

    You've got the base case so I'll continue from there.

    Let $\displaystyle 11^k - 6$ be divisible by 5 for some positive integer k. Then we may define:
    $\displaystyle 11^k - 6 = 5x$
    where x is some positive integer.

    We wish to show that $\displaystyle 11^{k + 1} - 6$ is divisible by 5. So:
    $\displaystyle 11^{k + 1} - 6 = 11 \cdot 11^k - 6$

    Now recall that $\displaystyle 11^k - 6 = 5x$
    So
    $\displaystyle 11^k = 5x + 6$

    Thus
    $\displaystyle 11^{k + 1} - 6 = 11 (5x + 6) - 6$

    $\displaystyle = 55x + 66 - 6$

    $\displaystyle = 55x + 60$

    $\displaystyle = 5(11x + 12)$

    Since x is an integer, so is 11x + 12. Thus etc.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, frostking2!

    Another approach . . .


    Prove by induction: .$\displaystyle 11^n - 6$ is divisible by 5 for all $\displaystyle n \geq 1$

    Verify $\displaystyle S(1)\!:\;\;11^1 - 6 \:=\:5$ . . . True!

    Assume $\displaystyle S(k)\!:\;\;11^k - 6 \:=\:5a$ for some integer $\displaystyle a.$


    Add $\displaystyle {\color{blue}10\!\cdot11^k}$ to both sides: .**

    . . $\displaystyle {\color{blue}10\!\cdot\!11^k} + 11^k - 6 \;=\;{\color{blue}10\!\cdot\!11^k} + 5a$

    . . $\displaystyle (10 + 1)\!\cdot\!11^k - 6 \;=\;10\!\cdot11^k + 5a$

    . . $\displaystyle 11\!\cdot\!11^k - 6 \;=\;10\!\cdot\!11^k + 5a$

    . . $\displaystyle 11^{k+1} - 6 \;=\;5\underbrace{\left(2\!\cdot\!11^k + a\right)}_{\text{an integer}} $

    Therefore: .$\displaystyle 11^{k+1}-6$ is divisible by 5.


    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

    **

    How did I know what to add? . . . Simple!

    I want: .$\displaystyle 11^k - 6 + {\color{red}X} \;=\;11^{k+1}-6$

    . . Then: .$\displaystyle {\color{red}X} \;=\;11^{k+1} - 11^k \;=\;11^k(11 - 1)$

    Therefore: .$\displaystyle {\color{red}X} \:=\:10\cdot11^k$ . . . . see?

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2007
    Posts
    17
    Soroban and Physics Maestro,

    Thanks so much for your time and effort. Each time someone explains a little differently I am able to understand it better. I am so glad you are willing to help! Have a great weekend.
    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: Oct 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: Mar 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum