Advanced GMAT Quant: Sequence question

[aramak]

I came across the following problem on page 142 of the Advanced GMAT Quant guide:

The sequence Xn is defined as follows: Xn = 2Xn-1 - 1 whenever n is an integer greater than 1. If X1 = 3, what is the value of X20 - X19 ?

Note: Subscripts have been colored blue.

The book goes on to recommend using a pattern recognition approach that involves computing the first 7 terms of the sequence and determining that the difference between consecutive terms in the sequence are all powers of 2.

I was wondering if there was an alternate approach to this problem that could employ the technique described on page 166 of the Equations, Inequalities, and VICs guide.

Specifically, my question is: Is there any straightforward way to convert the recursive sequence formula above into a direct formula? If I had the direct formula, I could easier compute the 19th and 20th terms in the sequence, along with their difference.

Also, what should my thought process be when I am trying to determine whether to go the route of computing the direct formula vs. pattern matching when solving problems involving sequences?

Thanks in advance!

Anand

[jnelson0612]

Greetings Anand!

I'm not seeing a way because of the exponential nature of the problem . . . since we don't have a linear equation I'm not seeing a way to find a formula. Honestly, if there were one I'm sure it would be included in this book and the fact that the book recommends that you handle the problem in this particular way indicates to me that a good way to handle it with a formula does not exist.

Good question!

[pawan.gupta.2006]

Hi,

May I offer a solution?

Solution:

X20-X19 = (2X19-1) - (X19) = X19 - 1

What this tell us? It tells us that the difference between any two consecutive numbers differs by -1.

so, common difference (d) = -1
we also have X1 = 3

So, now, X19 = X1 + d(19-1) [as per the standard formula]

X19 = 3 - 1(19-1) = 3 - 1(18) = 3-18 = -15

As we just deduced, X20-X19 = X19-1 = -15-1 = -16

I think that's the way to do it. I may be completely off here.

Pawan

[pawan.gupta.2006]

Hi,

May I offer a solution?

Solution:

X20-X19 = (2X19-1) - (X19) = X19 - 1

What does this tell us? It tells us that the difference between any two consecutive numbers differs by -1.

so, common difference (d) = -1
we also have X1 = 3

So, now, X19 = X1 + d(19-1) [as per the standard formula]

X19 = 3 - 1(19-1) = 3 - 1(18) = 3-18 = -15

As we just deduced, X20-X19 = X19-1 = -15-1 = -16

I think that's the way to do it. I may be completely off here.

Pawan

[messi10]

Hi Pawan,

That is a nice try but I think your answer is not correct. Without doing any calculations, you can see that any term is twice the value of the previous term minus 1 and since the first term is positive, we can safely assume that as n increases, so will the value of the corresponding terms. This means that our answer will be positive and yours is unfortunately negative.

As Jamie has pointed out - given the exponential nature of the problem, the method described in the book is the best way. Also, this question is actually deceptively simple when you think about what it is asking for. With any question, whether it be a 300 or 700 level question, we have to always keep in mind what we are solving for.

Even before we start any calculations, we can see that this question is asking for the difference between the 19th and the 20th term. Its not actually asking for the values of the two terms. In short, its asking us to recognize the pattern between two terms. The two terms are far away in the sequence (19 and 20) and we can assume that there is a pattern to begin with and its not just an arbitrary sequence. GMAT will never give a question that requires copious amount of calculations.

Regards

Sunil

[tim]

thanks Sunil!

[deepak.salwan]

Here's my take on the answer...

If you calculate the values of each term as per the given formula, it turns out to be ... X1 = 3, X2= 5, X3=9, X4=17, X5=33... These term values can be rewritten in the form of exponents; so they will look like this ... X1 = 1+2^1 , X2 = 1+2^2, X3= 1+2^3...
Now this can be converted to a sequence which looks like..

Xn = 1+2^n

Now X20 = 1+2^20
= 1+((2^19) * 2 ^1)
X19 = 1+2^19

X20 - X19 = 1+((2^19) * 2 ^1)) - (1+2^19)
= 2^19(2-1)
= 2^19

Hope I am right about this approach. Now what I don't know is whether 2^19 is enough as an answer or I need to further solve it to the actual value. If yes, then can some help me if there is a formula to calculate large exponent values ? though I have an observation this below..

2^1 = 2; ends in 2
2^2 = 4; ends in 4
2^3 = 8; ends in 8
2^4 = 16; ends in 6
2^5 = 32; ends in 2
2^6 = 64; ends in 4
2^7 = 128; ends in 8
2^8 = 256; ends in 6

The ending digits are repeated (2,4,8,6 .. ) after every 4th exponent. Going by this, value of 2^19 must have an ending digit of 8.

Cheers,
Deepak

[JohnHarris]

...Now what I don't know is whether 2^19 is enough as an answer or I need to further solve it to the actual value. ...

Hi Deepak,

Well since everyone should know that 2^10 = 1024 and multiplying 1024 by itself and dividing by 2 should be 'fast' and the answer is x19 -1, see previous,
the answer is

2^19 + 1 - 1 = (2^20)/2 = 524288

Just kidding :-). I really think 2^19 is a good answer and you don't need to go further.

[tim]

it really all depends on what form the answer choices take. John is right though that everyone should know their powers of 2 up to 2^10, so calculating 2^19 is feasible even if you are not likely to see such a calculation being required on the GMAT..