1. Not finding help here? Sign up for a free 30min 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!

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...