1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof by Induction

  1. Aug 23, 2009 #1
    1. The problem statement, all variables and given/known data

    http://img200.imageshack.us/img200/7097/99175506.gif [Broken]

    2. Relevant equations

    3. The attempt at a solution

    For [tex]n \in N[/tex] let P(n) be the statement: "81 | (10n+1-9n-10)"

    Base Case: when n=1: 10n+1-9n-10 = 81 = 81 × 1

    So P(1) is true

    Inductive Step: let [tex]k \in N[/tex] and suppose [tex]P(k)[/tex] is true, that is 81 | (10k+1-9k-10) is true. Then [tex]10^{k+1}-9k-10=81m[/tex] for some [tex]m \in Z[/tex]. Then [tex]10^{k+1}=(81m+9k+10)[/tex].


    10k+2-10(k+1)-10=10 × 10k+1-10(k+1)-10

    =10 × (81m+9k+10)-10k+10-10

    = 10 × (81m+9k+10-k)

    I'm stuck here and I don't know how to factor things out and bring the 81 forth to get the expression in the form: "81(something here)" to show that it's divisible by 81 for all n. Any help is appreciated.

    I might be able to do it this way:

    10 × (81m+9k+10-k) = 810m+90k+100-10k
    => 81(10m+(90/81)k+(100/81)-(10/81)k)

    But I don't feel that this is the right way...
    Last edited by a moderator: May 4, 2017
  2. jcsd
  3. Aug 23, 2009 #2


    User Avatar
    Homework Helper

    That is how you'd arrive at your answer.
  4. Aug 23, 2009 #3
    It's a bit awkward... are you sure that there is not a better way?
  5. Aug 23, 2009 #4
    You have a few typos in your inductive step (should be 9(k+1), not 10(k+1)).

    Note that
    [tex]10^{(k+1)+1} - 9(k+1) - 10 = 10\cdot10^{k+1} - 9k - 9 - 10 = 10(10^{n+1} - 9n - 10) + 81n + 81[/tex]
  6. Aug 23, 2009 #5
    How did you get from [tex]10\cdot10^{k+1} - 9k - 9 - 10[/tex] to [tex]10(10^{n+1} - 9n - 10) + 81n + 81[/tex]? Could you please explain :)

    Yes that was a typo but I thought it would be a good way to replace 10k+1 by 81m+9k-10, since [tex]10^{k+1}-9k-10=81m \Rightarrow 10^{k+1} = 81m+9k+10[/tex]
  7. Aug 23, 2009 #6
    The above looks good, without some typos. Should be:
    10k+2-9(k+1)-10=10 × 10k+1-9(k+1)-10

    Then keep going.
    Last edited by a moderator: May 4, 2017
  8. Aug 23, 2009 #7
    You always want to apply the inductive hypothesis as easily as possible. If the inductive step gives you
    [tex]10^{(k+1)+1} - 9(k+1) - 10 = 10\cdot10^{(k+1)} - 9(k+1) - 10 ,[/tex]
    then the fact that you can pull out the very first 10 factor on the right hand side suggests multiplying the expression [tex]10^{(k+1)} - 9k - 10[/tex] in our inductive hypothesis by 10 and relating it to the inductive step somehow.
  9. Aug 23, 2009 #8


    User Avatar
    Homework Helper

    [tex]H_N: 10^{N+1}-9N-10=81m[/tex]




    [tex]10^{N+2}-90(N+1)-10=810m \Rightarrow 10^{N+2}-9(N+1)-10=810m+81(N+1)[/tex]

    Left side happens to be HN+1 and the right side is divisible by 81 no matter what N is.....

    so even if it is awkward, once you show it is divisible by 81, you have proven it.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook