Results 1 to 10 of 10

Math Help - prove Xn is even

  1. #1
    Newbie
    Joined
    Jul 2009
    Posts
    23

    prove Xn is even

    In an infinite sequence {Xn} of positive integers , Xn+1 is the sum of Xn and a non zero digit of Xn for n>=1. Prove that Xn is even for some n>=1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2008
    From
    Melbourne Australia
    Posts
    195
    Thanks
    13
    Quote Originally Posted by nh149 View Post
    In an infinite sequence {Xn} of positive integers , Xn+1 is the sum of Xn and a non zero digit of Xn for n>=1. Prove that Xn is even for some n>=1.
    Assume Xn is even for all n>1

    Each successive value in the sequence is formed by adding a number between 1 and 9. Given that Xn is odd we can not add an odd number so Xn+1-Xn = 2,4,6 or 8.

    Let's define the symbol ? to be a generic odd digit, So ???2 is the four digit number with three odd digits and ends in 2.

    First argue that one of the terms must have the form:

    ??2, ??4, ??6 or ??8

    The next term is odd!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Um ... I might be misunderstanding the question but ...

    if we consider the sequence of positive integers, i.e. {1,2,3,4,...}, isn't it clear that not all x_n is even for n \geq 1?

    so it wouldn't be true for just any infinite sequence of positive integers ....
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    732
    Ah yes but in \{1, 2, 3, 4, ...\} this does not fit the pattern: 4 is not the sum of 3 and one of the digits of 3. Neither is 3 the sum of 2 and one of the digits in 2. And so on.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    732
    Quote Originally Posted by Kiwi_Dave View Post
    Assume Xn is even for all n>1

    Each successive value in the sequence is formed by adding a number between 1 and 9. Given that Xn is odd we can not add an odd number so Xn+1-Xn = 2,4,6 or 8.

    Let's define the symbol ? to be a generic odd digit, So ???2 is the four digit number with three odd digits and ends in 2.

    First argue that one of the terms must have the form:

    ??2, ??4, ??6 or ??8

    The next term is odd!

    You've confused me - aren't we trying to assume that there exists an EVEN number in the sequence? You've done the opposite - you supposed that they are all even and proved that there has to be an odd number.

    I'm not sure I believe your proof either, sorry pal ...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    OH!!! HAHAHA ... silly me ... I thought that Xn+1 was just a notation for \sum_{i=1}^nx_n+x_a where 1\leq a \leq n ... it's supposed to be the next term ...

    Then I'm also assuming that the sequence starts at n=0 since if we start with n_1 as an odd number, it doesn't work.

    Um ... it works for single digits, but once you get more than one digit, it doesn't always work.

    Consider this part of the the infinite sequence: 1,2,4,8,16

    The next number is either 16 + 1 or 16 + 6 ... which is 17 or 22 ... 17 is odd ... doesn't work

    Again, if I'm misunderstanding something, my apologies


    P.S. First misunderstanding was due to my brain thinking too much about another problem
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Sorry, tried to edit my previous post, but I guess it's still being reviewed.

    I'm not sure how to show this clearly because there's alot of "choosing" involved.

    If we start with a single digit number, then the case is trivial, because the next number will be twice that single digit (i.e. 2 times that number).

    If we start with a multiple digit number, and we try to keep the integers to be odd (by adding an appropriate digit to x_n), what will happen is that we will end up with an odd integer with all digits odd, so we are forced to add two odd numbers, which results in an even number.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    732
    Quote Originally Posted by Bingk View Post
    Sorry, tried to edit my previous post, but I guess it's still being reviewed.

    I'm not sure how to show this clearly because there's alot of "choosing" involved.

    If we start with a single digit number, then the case is trivial, because the next number will be twice that single digit (i.e. 2 times that number).

    If we start with a multiple digit number, and we try to keep the integers to be odd (by adding an appropriate digit to x_n), what will happen is that we will end up with an odd integer with all digits odd, so we are forced to add two odd numbers, which results in an even number.
    What needs to be proved then is:

    In the given sequence, there will be a number such that all the digits are odd. I'm not sure we've proved that yet.

    We know that we can create such a sequence such that *all* the numbers in it are even - just start with 2 and always add the last digit.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Yeah, I don't know how exactly to show that, but this is basically what happens:

    Say we start with an odd number with an even digit. Now, notice that adding the even number is basically adding a multiple of 2. Each time we add a multiple of 2 to the number, basically 2 things happen, either only the units digit changes, or the units and some succeeding digits change.

    The first case isn't really helpful since there's an even digit somewhere before the addition, and it's not in the units place (cuz then we'll have our even number).

    In the second case, what will happen is that some of the other digits after the units digit will increase by only 1.

    So, say we have an N digit odd number with only the units digit as odd, what we do is keeping adding even numbers until the Nth digit increases by 1, thus making it odd. Once it is odd, we do something similar for the N-1th digit, and we keep doing this all the way until the tens digit is the last even number. We keep adding a multiple of two until the tens digit becomes odd, and the units will still be odd (since we have an odd number). Thus, we have our odd digits odd number.

    I should note that only the Nth and units digit need be odd. We may make any of the other digits between be zero.

    Now that we have that number, our only option is to add the odd number with one of it's odd digits, and we get an even number! YAY!

    Hope that helps ... it's more of a constructional proof
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    May 2008
    From
    Melbourne Australia
    Posts
    195
    Thanks
    13
    Same idea, slightly different presentation:

    Let the first number in the sequence be "a" and let a be odd with n digits.

    Let X_m be the largest n digit member in the sequence, then

    X_m < 10^n

    so

    X_{m+1} < 10^n + 8

    but X_{m+1 }>= 10^n

    so we can write:

    10^n=< X_{m+1}<10^n+8

    Hence the most significant digit of X_{m+1} is 1.

    CASE 1 The least significant digit is even and the conjecture is true

    CASE 2 the least significant digit is odd. All other digits are zero and X_{m+2} is even.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove a/b and a/c then a/ (3b-7c)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 23rd 2010, 05:20 PM
  2. prove,,,
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 1st 2010, 09:02 AM
  3. Prove |w + z| <= |w| +|z|
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 28th 2010, 05:44 AM
  4. Replies: 2
    Last Post: August 28th 2009, 02:59 AM
  5. How to prove that n^2 + n + 2 is even??
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 30th 2008, 01:24 PM

Search Tags


/mathhelpforum @mathhelpforum