Can someone explain how that Tn = 2Tn-1 + 1 sequence actually works?
Asked
Active
Viewed 94 times
3 Answers
2
The subscript merely indicates which term of the sequence we are using. Thus, $T_n$ represents the value of the nth term of the sequence. The above interpretation applies equally well to any other term (eg. $n - 1$).
$T_n = 2T_{n-1} + 1$ means "to find the value of the nth term of the sequence, you need to find the value of $(n - 1)$th term first; then 2 times it; and then add 1 to it".
Marc van Leeuwen
- 115,048
Mick
- 17,141
1
The recurrence sequence is a sequence that each term is defined by its previous terms. Hence, the sequence must have the initial term. For example,
$T_n=2T_{n-1}+1.$ Assume that the sequence begin at $T_1.$
So, $T_2=2T_1+1$,
$T_3=2T_2+1=2(2T_1+1)+1=4T_1+3$ and so on.
We can see that if we do not know the value of $T_1$, we also can not find the value of $ T_2,T_3,...$
In fact, we can define recurrence relation that T_n is defined by T_{n-2}. For example,
$T_n=T_{n-2}+1$.
But in this case, the initial values must have 2 terms(T_1 and T_2).
If you want to find $T_{1000}$ of a recurrence sequence, you have to find $T_{999},T_{998},...$. It is not difficult, but it takes so much time. So, how can we find $T_{1000}$ without finding $T_{999}, T_{998},...$? That is the goal of recurrence equation.
Worawit Tepsan
- 656
-
Denote that General form or solution of recurrence sequence means $T_n$ is directly defined by only $n$ not from the previous term.
In fact, you can find a general form only some recurrence sequence. For example,
$T_n=T_{n-1} +1$ such that $T_1=1.$
You can easily see that $T_n=n$ is the solution or general form of the above sequence.
– Worawit Tepsan Oct 31 '13 at 05:40 -
If a recurrence sequence is complicated, it is also difficult to find a general solution for it. I thinks in that book will teach you methods for finding a general solution of some specific recurrence sequences. – Worawit Tepsan Oct 31 '13 at 05:50
-
Nevermind all... Got it... Rest will do wonders for a person LOL... Was just brain dead last night... Now it's clear... – Samuel Longgat Oct 31 '13 at 19:27
-
@WorawitTepsan How would we find out the recurrence equation in this case? – Sawarnik Feb 23 '14 at 07:02
0
A recurrence relation is a rule for generating a sequence of numbers (loosely). So let's say I give you a number, for instance $0$ and a rule: double your number and add 1. If you apply the rule repeatedly (starting with zero), you will get a sequence: $$(0,1,3,7,15,31,63,127...$$
More formally, we could say that $T_n$ is the $n$-th number in the sequence, starting from $n=0$. So for example, $T_0=0$, $T_1=1$ and $T_5=31$. Then the rule double your number and add 1 becomes: $$T_n=2T_{n-1}+1$$
Does this help?
Kieran Cooney
- 1,437
-
So $n$ (what we call the subscript) denotes the position in the sequence above. $T_0$ represents the first number,0. $T_1$ represents the second and so on. So $T_5$ means start from the first number in the sequence, and move to the right 5 times. So $T_{2}=3,T_{3}=7,T_{4}=15$ and so on. – Kieran Cooney Oct 31 '13 at 05:33
-
You definitely are plugging numbers in. The recurrence relation tells you how to get the next number in the sequence. So we know from above that $T_8=127$. We want to get the next number in the sequence. So here we take $n-1$ to be 8. So $n=(n-1)+1=9$. Plugging in these values into the recurrence relation: $T_9=2(T_{8})+1=2(127)+1=257. – Kieran Cooney Oct 31 '13 at 05:50
-
Is there any way to compute $T_{n}$ without computing the sequence before? Just curious. – Sawarnik Feb 22 '14 at 16:26
Thank you much
– Samuel Longgat Oct 31 '13 at 05:05