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

Originally Posted by nh149

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!

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 is even for ?

so it wouldn't be true for just any infinite sequence of positive integers ....

Ah yes but in 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.

Originally Posted by Kiwi_Dave

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

OH!!! HAHAHA ... silly me ... I thought that Xn+1 was just a notation for where ... it's supposed to be the next term ...

Then I'm also assuming that the sequence starts at since if we start with 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

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

Originally Posted by Bingk

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

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

Same idea, slightly different presentation:

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

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



so



but

so we can write:



Hence the most significant digit of 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 is even.