Page 1 of 2 12 LastLast
Results 1 to 15 of 23
Like Tree1Thanks

Math Help - induction

  1. #1
    Newbie
    Joined
    Nov 2013
    From
    on my pc
    Posts
    14

    induction

    prove by induction:


    10^n+1 + 3.10^n + 5 is a multiple of 9, ∀n ∈ ℕ
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1

    Re: induction

    Quote Originally Posted by beast View Post
    prove by induction:


    10^n+1 + 3.10^n + 5 is a multiple of 9, ∀n ∈ ℕ
    Base case is easy. So assume we know the theorem is true for some n = k. That means
    10^{k + 1} + 3 \cdot 10^k + 5 = 9m
    where m is some integer.

    We need to show that
    10^{k + 2} + 3 \cdot 10^{k + 1} + 5
    is divisible by 9.

    To this end, solve the "k" equation for 10^{k+1}
    10^{k + 1} =  -3 \cdot 10^k - 5 + 9m

    Multiply both sides by 10 so you get that
    10^{k + 2} = -3 \cdot 10^{k+1} - 50 - 9m

    Plug this into your "k + 1" case.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2013
    From
    on my pc
    Posts
    14

    Re: induction

    thanks but im new to this so i don't understand what your saying.
    my lecturer does not teach well. :/
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1

    Re: induction

    Quote Originally Posted by topsquark View Post
    Base case is easy. So assume we know the theorem is true for some n = k. That means
    10^{k + 1} + 3 \cdot 10^k + 5 = 9m
    where m is some integer.

    We need to show that
    10^{k + 2} + 3 \cdot 10^{k + 1} + 5
    is divisible by 9.

    To this end, solve the "k" equation for 10^{k+1}
    10^{k + 1} =  -3 \cdot 10^k - 5 + 9m

    Multiply both sides by 10 so you get that
    10^{k + 2} = -3 \cdot 10^{k+1} - 50 - 9m

    Plug this into your "k + 1" case.

    -Dan
    Okay. First: Do you understand why 9m appears in the first line? Do you understand how I derived the 10^(k + 2) expression in the last line?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2013
    From
    on my pc
    Posts
    14

    Re: induction

    i understand the 9m but i dont get the 10 ^ (k+2)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1

    Re: induction

    Quote Originally Posted by topsquark View Post
    10^{k + 2} + 3 \cdot 10^{k + 1} + 5
    is divisible by 9.

    To this end, solve the "k" equation for 10^{k+1}
    10^{k + 1} =  -3 \cdot 10^k - 5 + 9m

    Multiply both sides by 10 so you get that
    10^{k + 2} = -3 \cdot 10^{k+1} - 50 - 9m

    Plug this into your "k + 1" case.
    We have
    10^{k + 1} =  -3 \cdot 10^k - 5 + 9m
    from the n = k assumption.

    Now multiply both sides by 10:
    10 \cdot 10^{k + 1} =  -30 \cdot 10^k - 50 + 90m

    I'm going to reset m to be such that 90m --> 9m. (I suppose I should change the variable to "a" so that 90m = 9a or something.)

    10^{k + 2} =  -3 \cdot 10^{k + 1} - 50 + 9m

    You need to show that
    10^{k + 2} + 3 \cdot 10^{k + 1} + 5
    is divisible by 9. Plug the above expression into this line.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Nov 2013
    From
    on my pc
    Posts
    14

    Re: induction

    ok i now understand the k+2 part
    my lecturer never thought us that.

    im now lost after this part:

    I'm going to reset m to be such that 90m --> 9m. (I suppose I should change the variable to "a" so that 90m = 9a or something.)

    10^{k + 2} = -3 \cdot 10^{k + 1} - 50 + 9m

    You need to show that
    10^{k + 2} + 3 \cdot 10^{k + 1} + 5
    is divisible by 9. Plug the above expression into this line.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1

    Re: induction

    10^{k + 2} =  -3 \cdot 10^{k + 1} - 50 + 9m

    So
    10^{k + 2} + 3 \cdot 10^{k + 1} + 5

    = \left ( -3 \cdot 10^{k + 1} - 50 + 9m \right ) + 3 \cdot 10^{k + 1} + 5

    Is this divisible by 9?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Nov 2013
    From
    on my pc
    Posts
    14

    Re: induction

    i honestly dont know...
    there are some students in my class who are repeating this course for the 3rd time :/
    can you please do the entire sum and explain it line by line. that would really help. the induction divisibility questions give me alot of trouble.
    what are some tips on how to do them?
    I appreciate any help rendered.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,879
    Thanks
    742

    Re: induction

    You want the end result to be 9(\text{expression that evaluates to an integer}). Nine times an integer is a multiple of nine. So, topsquark gave you the solution. Just simplify and factor out a nine.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Nov 2013
    From
    on my pc
    Posts
    14

    Re: induction

    how do i simplify and factor out 9?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,879
    Thanks
    742

    Re: induction

    Simplify means combine like terms. You factor out a nine by dividing each remaining term by 9.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Nov 2013
    From
    on my pc
    Posts
    14

    Re: induction

    would it be 3.10^(k+1) -45 + 9m is divisible by 9?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,879
    Thanks
    742

    Re: induction

    What happened to the -3\cdot 10^{k+1}?

    It is difficult to assist you when you are not familiar with the process of simplifying expressions. I recommend a thorough review of algebra.
    Last edited by SlipEternal; November 4th 2013 at 01:05 PM.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,670
    Thanks
    1618
    Awards
    1

    Re: induction

    Quote Originally Posted by beast View Post
    prove by induction:
    10^n+1 + 3.10^n + 5 is a multiple of 9, ∀n ∈ ℕ
    Lets start over. P(n)=10^{n+1}+3\cdot 10^n+5.
    We want to show that P(n) is a multiple of nine for each positive integer n.

    To get going look at P(1)=135 which is a multiple of nine( the digit sum is 9).

    Lets say for positive integer K\ge 1 and we know that P(K)=10^{K+1}+3\cdot 10^K+5 is a multiple of nine.

    The next one up is P(K+1). So lets look at it.

    P(K+1)=10^{K+2}+3\cdot 10^{K+1}+5=10(\underbrace {{{10}^{K + 1}} + 3 \cdot {{10}^K} + 5}_{\text{multiple of nine}})-45 is that correct?
    Now we have the difference of two multiples of nine.

    So from any point we have shown that the next one up works.
    We know P(1) is a multiple of nine so P(2) is a multiple of nine.
    We just keep going through all positive integers.
    Last edited by Plato; November 4th 2013 at 01:49 PM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Induction
    Posted in the Algebra Forum
    Replies: 8
    Last Post: March 3rd 2010, 11:27 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 1st 2007, 04:44 AM

Search Tags


/mathhelpforum @mathhelpforum