Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Series math problem

  1. Sep 15, 2005 #1
    [tex]n_1 = 1[/tex]

    [tex]a_1 = 1[/tex]

    [tex]n_i = i[/tex]

    [tex]a_i = 8 a_{i-1} + 1[/tex]

    Is it possible to show that [tex]a_i - n_i[/tex] is a multiple of 7 for all [tex]i > 1[/tex]?
     
    Last edited by a moderator: Sep 15, 2005
  2. jcsd
  3. Sep 15, 2005 #2

    selfAdjoint

    User Avatar
    Staff Emeritus
    Gold Member
    Dearly Missed

    By my calculation, for i=2 you have a_2 = 8(a_1)+1 = 9, while n_2 = 2. So a_2 - n_2 = 7. And it just gets worse, since the a sequence is essentially geometric and the n sequence is arithmetic.
     
  4. Sep 15, 2005 #3
    Well, here are the first few values of this series:

    n_i a_i
    1 1
    2 9
    3 73
    4 585
    5 4681
     
  5. Sep 15, 2005 #4

    LeonhardEuler

    User Avatar
    Gold Member

    You can do a proof by induction. For your inductive step it will be useful to express [itex]a_{n-1}[/itex] in a congruence mod 7.
     
  6. Sep 16, 2005 #5

    VietDao29

    User Avatar
    Homework Helper

    First, you can do something like this in paper:
    ai = 8ai - 1 + 1 = 8(8ai - 2 + 1) + 1 = 82ai - 2 + 8 + 1 = 82(ai - 3 + 1) + 81 + 1 = 83ai - 3 + 82 + 81 + 1 = 84ai - 4 + 83 + 82 + 81 + 1 = 84ai - 4 + 83 + 82 + 81 + 80 (since 80 = 1) ... and finally, you can relate ai and a1.
    So ai = 8i - 1ai - (i - 1) + 8i - 2 + 8i - 3 + ... + 82 + 81 + 80 = 8i - 1a1 + 8i - 2 + 8i - 3 + ... + 82 + 81 + 80 = 8i - 1 + 8i - 2 + 8i - 3 + ... + 82 + 81 + 80 (Since a1 = 1).
    So you have:
    [tex]a_i = \sum_{k = 0} ^ {i - 1} 8 ^ k[/tex] (1), for all i >= 1.
    This part helps you get the relation between ai and i (but it's not a proof), then you can prove (1) by induction.
    --------------
    So [tex]a_i - i = \left( \sum_{k = 0} ^ {i - 1} 8 ^ k \right) - i[/tex].
    Note that [tex]8 \equiv 1 \mbox{ mod } 7[/tex].
    So what can you say about: [tex]\sum_{k = 0} ^ {i - 1} 8 ^ k \equiv ? \mbox{ mod } 7[/tex]
    Viet Dao,
     
    Last edited: Sep 16, 2005
  7. Sep 16, 2005 #6
    I'll give it a shot.
     
  8. Sep 16, 2005 #7

    LeonhardEuler

    User Avatar
    Gold Member

    Actually, the problem is pretty simple. What you have to prove is that
    [tex]a_n - n\equiv 0 mod7[/tex]
    or
    [tex]a_n\equiv n mod7[/tex]
    You know that for n=2 this is true. Now suppose
    [tex]a_{n-1}\equiv(n-1) mod 7[/tex]
    Then
    [tex]a_n=8a_{n-1} +1 = 7a_{n-1} +a_{n-1} +1\equiv a_{n-1} +1mod7[/tex]
    It is easily taken from there to show that this is congruent to n.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Series math problem
  1. Maths problem (Replies: 1)

  2. Math problems? (Replies: 2)

  3. Math Problem (Replies: 2)

  4. Math problem (Replies: 3)

Loading...