# Sequences : Question

• Jan 7th 2011, 05:12 AM
dumluck
Sequences : Question
Hi All,
I was wondering if you could help me with the below...

. If the sequence x(1), x(2), x(3), …, x(n), … is such that x(1) = 3 and x(n+1) = 2x(n) – 1 for n ≥ 1, then x(20) – x(19) =

A. 2^19
B. 2^20
C. 2^21
D. (2^20) - 1
E. (2^21) - 1

I'm drawing a complete blank. x(n+1) = 2x(n) - 1 would ellude to x(20) being 2x(value of 19) -1. = 2x(19) - 1 = 38x - 1 which seems completely off? Do I have to substitute all the way from x(1) to x(19) to determine the value?

• Jan 7th 2011, 06:01 AM
emakarov
Quote:

2x(19) - 1 = 38x - 1 which seems completely off?
Yes, this is off because x is a function from natural numbers to natural numbers; it is not a number. Thus, x(19) is a number, but 2x and 38x don't make sense.

I'll write the argument of x as a subscript: $x_n$ instead of $x(n)$. By definition, $x_{20}-x_{19} = 2x_{19}-1-x_{19}=x_{19}-1$. After that, the first idea that came to mind was to guess the general formula for $x_n$ by calculating the first several values of $x_n$ and, possibly, to prove this general formula by induction.

$\begin{array}{c|c|c|c|c|c|c|c}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline
x_n & 3 & 5 & 9 & 17 & 33 & 65 & 129
\end{array}$

Can you guess the general formula for $x_n$?
• Jan 7th 2011, 06:17 AM
dumluck
Quote:

Originally Posted by emakarov
Yes, this is off because x is a function from natural numbers to natural numbers; it is not a number. Thus, x(19) is a number, but 2x and 38x don't make sense.

I'll write the argument of x as a subscript: $x_n$ instead of $x(n)$. By definition, $x_{20}-x_{19} = 2x_{19}-1-x_{19}=x_{19}-1$. After that, the first idea that came to mind was to guess the general formula for $x_n$ by calculating the first several values of $x_n$ and, possibly, to prove this general formula by induction.

$\begin{array}{c|c|c|c|c|c|c|c}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline
x_n & 3 & 5 & 9 & 17 & 33 & 65 & 129
\end{array}$

Can you guess the general formula for $x_n$?

ekkk Is it ....
$X_n = 2(X_{n-1} - X_{n-2}) + X_{n-1} ?$

Could you elaborate on the substitution that resulted in $x_{20}-x_{19} = 2x_{19}-1-x_{19}=x_{19}-1$. I'm not sure where the $-x_{19}$ came from?
• Jan 7th 2011, 06:17 AM
Plato
• Jan 7th 2011, 06:52 AM
emakarov
Quote:

Originally Posted by dumluck
ekkk Is it ....
$X_n = 2(X_{n-1} - X_{n-2}) + X_{n-1} ?$

By "general formula" I meant "a closed-form solution: a non-recursive function of n" (Wikipedia). Your expression for $x_n$ is still recursive because it refers (recurs) to $x_{n-1}$.

Quote:

Could you elaborate on the substitution that resulted in $x_{20}-x_{19} = 2x_{19}-1-x_{19}=x_{19}-1$.
By definition, $x_{n+1}=2x_{n}-1$. Substituting n = 19, we get $x_{20}=2x_{19}-1$. Subtracting $x_{19}$ from both sides, we get $x_{20}-x_{19}=2x_{19}-1-x_{19}$.
• Jan 7th 2011, 06:58 AM
dumluck
Quote:

Originally Posted by emakarov
By "general formula" I meant "a closed-form solution: a non-recursive function of n" (Wikipedia). Your expression for $x_n$ is still recursive because it refers (recurs) to $x_{n-1}$.

By definition, $x_{n+1}=2x_{n}-1$. Substituting n = 19, we get $x_{20}=2x_{19}-1$. Subtracting $x_{19}$ from both sides, we get $x_{20}-x_{19}=2x_{19}-1-x_{19}$.

Ah yes.. thanks. Would this not be it then

$x_{n} = 2x_{n} - 1$
• Jan 7th 2011, 07:08 AM
emakarov
Quote:

Originally Posted by dumluck
Would this not be it then

$x_{n+1} = 2x_{n} - 1$

This is the definition, not the solution. As Plato's link says, $x_n=2^n+1$.
• Jan 7th 2011, 07:08 AM
Soroban
Hello, dumluck!

emakarov gave you an excellent hint.
. . But you didn't catch it, did you?

Quote:

$\begin{array}{c|c|c|c|c|c|c|c}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline
x_n & 3 & 5 & 9 & 17 & 33 & 65 & 129
\end{array}$

Can you guess the general formula for $\,x_n$?

Each number is one more than a power of 2.

. . $\begin{array}{ccc}
3 &=& 2^1 + 1 \\
5 &=& 2^2 + 1 \\
9 &=& 2^3 + 1 \\
17 &=& 2^4 + 1 \\
33 &=& 2^5 + 1 \\
\vdots && \vdots \end{array}$

Hence: . $x(n) \:=\:2^n+1$

Therefore: . $x(20) - x(19) \;=\;(2^{20}-1) - (2^{19}-1)$

. . . . . . . . . . $=\;2^{20} - 2^{19} \;=\;2^{19}(2 - 1) \;=\;2^{19}$ . answer A

• Jan 7th 2011, 07:15 AM
dumluck
ahh yes I see. Although the level of hint I would need to get that would be ... It's something to the power of 2 :). So all I had to do was transform the definition to the solution for Xn? moving the x to the other side. Thanks guys, much appreciated. Learnt a lot there. I love this forum.
• Jan 7th 2011, 10:28 AM
Quote:

Originally Posted by dumluck
Hi All,
I was wondering if you could help me with the below...

. If the sequence x(1), x(2), x(3), …, x(n), … is such that x(1) = 3 and x(n+1) = 2x(n) – 1 for n ≥ 1, then x(20) – x(19) =

A. 2^19
B. 2^20
C. 2^21
D. (2^20) - 1
E. (2^21) - 1

I'm drawing a complete blank. x(n+1) = 2x(n) - 1 would ellude to x(20) being 2x(value of 19) -1. = 2x(19) - 1 = 38x - 1 which seems completely off? Do I have to substitute all the way from x(1) to x(19) to determine the value?