Expert: Josh - 1/18/2009

Question
Hi!

I have two questions about finding an expression to represent a pattern so that one does not have to calculate each term before to find the Nth term.

(1). Is there an expression that lets one find the Nth term of a pattern without calculating each previous term for EVERY PATTERN?

(2). This is the given pattern. 3, 7, 13, 21, 31, 43 . . .

The terms increase by multiples of 2 each time, e.g. the difference between 3 and 7 is 2(2); the difference between 7 and 13 is 2(3); the difference between 13 and 21 is 2(4); etc.

The question asks me to find an expression that will let us find any term without having to calculate the previous terms.

Let's say I had to find the 100th term without calculating the 99th, 98th, 97th, 96th, etc.

If N is the number of the term, and X is the term, my understanding is that I need to find X in terms of N. How would I do this?

Thank you very much, I appreciate you taking your time to answer my question.

-Susan

Answer
Hi Susan,

Broadly speaking, sequences fall into one of two categories: deterministic ones and random ones.

The former means that we can find an expression to describe each term exactly. The latter cannot be represented exactly, but we can generally find an expression which minimizes the distortion resulting from approximation with respect to some statistical measure (such as mean square error).

Your inquiry falls into the first category, so we can in theory predict the sequence perfectly, provided we know its structure.

Ans:(part 1)  Let's consider the case where knowing the past is sufficient to predict the future. The question of how far we need to go back in history to predict the future term is an attribute of the sequence. Some may show long range dependence (perhaps on its infinite past, although in practice the influence of previous terms often decay rapidly in time) while others depend only on its short recent history. In your question, the sequence can be described by a first order difference equation. That is to say, the term T[n] at time step n depends only on the previous term T[n-1] at time step n-1. So, if we already know the value of term T[n-1], we don't need to calculate each previous term from the beginning in order to find T[n].

Ans:(part 2)  The pattern is as follows: The difference between the current term and previous term is twice the value of the current time step. i.e., (T[n]-T[n-1])=2*n for n=2,3,...etc. We must also specify an initial value T[1]=3.

Testing this formula, T[n]=2n+T[n-1], when n=2, T[2]=4+3=7.

Ans:(part 3)  I understand your question now. We need to write T[n] recursively and make a few observations along the way.

T[n]=2n+T[n-1], substituting T[n-1]=2(n-1)+T[n-2]
   =2n+2(n-1)+T[n-2], repeating this argument a few times (some steps omitted)
   =2n+2(n-1)+2(n-2)+...+base_term

Observation 1: The base_term has the form 2(n-K)+T[n-K-1]. This procedure terminates in the base case n-K-1=1, we have the known value T[1]=3 when K=n-2. Thus, T[n]=2[n+(n-1)+(n-2)+...+2]+T[1].

Observation 2: The first component consists of "n+(n-1)+(n-2)+...+2", an expression that is related to an arithmetic sum.
Of course, N = n+(n-1)+(n-2)+...+2 = [1+2+...+(n-2)+(n-1)+n] - 1.
Using the arithmetic sum formula, SUM i from i=1 to i=n equals (1+n)*(n/2), N = (1+n)*(n/2) - 1.

Finally, T[n]=2*[(1+n)*(n/2)-1]+3.

e.g., when n=4, T[4] = 2[5*4/2-1]+3 = 21.
     when n=100, T[100] = 2[101*50-1]+3 = 10101....i think