Expert: Josh - 6/9/2006

Question
Complete the Series…

1

1 1

2 1

1 2 1 1

3 1 1 2

? ? ? ? ? ?

Give logic in support of your answer.


Answer
There's no definitive answer to this question.
The patterns can be rationalized in various ways. Different people will see different things.
One particular interpretation is given below.

Compare the entries with the following structure.

T(0,0)
T(1,0) T(1,1)
T(2,0) T(2,1)
T(3,0) T(3,1) T(3,2) T(3,3)
T(4,0) T(4,1) T(4,2) T(4,3)
T(5,0) T(5,1) T(5,2) T(5,3) T(5,4) T(5,5) T(5,6) T(5,7)

Here, T(r,c) is the cth element in row "r". I am going to argue that the sequence in row r contains R(r)=2^(ceiling(r/2)) elements; where ceiling(x) rounds x up to the nearest integer. [Plug in a few numbers to make sense of this. e.g., when r=5, the sequence is supposed to contain R(5)=2^(ceil(5/2))=2^(round_up(2.5))=2^3=8 elements]

Assume that the initial terms are given by T(0,0)=1 and T(1,0)=T(1,1)=1. Remember, the value R(r) is fixed (simply a constant) for a given row r.

For row r, one particular observation is as follows.

If r+c is even,
 T(r,c)=T(r-1,c)+T(r-2,c) for 0<=c<R(r)/2 .....[#1]

If r+c is odd,
 T(r,c)=T(r-1,c)-T(r-2,c) for 0<=c<R(r)/2 .....[#3]

[i.e., If the row and column indices add up to an even integer, the first half of the entries in sequence r are formed by adding the corresponding entries in the same column from the two previous rows. If the row and column indices add up to an odd integer, the first half of the entries in sequence r are formed by subtracting the corresponding entry in row r-1 from the corresponding entry in row r-2. ]

Now, let's say a few things about remaining entries.

If r is odd,
 T(r,c)=T(r-2,c-(R(r)/2))   for R(r)/2 <=c < R(r) .....[#2]
If r is even,
 T(r,c)=T(r-2,R(r-2)-1-[c-(R(r)/2)])   for R(r)/2 <=c < R(r) .....[#4]
 
[i.e., When the index r is even, the second half of the entries are formed by duplicating sequence r-2. When the index r is odd, the second half of the entries in sequence r are formed by copying entries in sequence r-2, but in reverse order.]

The expression looks rather complicated, but the rule is quite easy to implement in practice.

Note: We cannot be certain whether this pattern actually is the one constructed by the person who set this question. We can only justify our choice by checking that it is consistent with the pattern thus far.

Illustration:
When r=2, we have R(r)=2 elements in sequence 2. So, R(r)/2=1. Look at the sequences now.
1
1 1
2 1
Since r is even, for entries in the first half of the sequence, we compute each term using [#1].
Observe that for 0<=c<1,
T(2,0)=T(1,0)+T(0,0)=1+1=2
For entries in the second half of the sequence, we compute each term using [#4]. Here, row r-2=0 contains R(r-2)=2^(0)=1 element.
Observe that for 1<=c<2, the complicated looking index R(r-2)-1-[c-(R(r)/2)] evaluates to (1-1)-[1-(2/2)]=0, we have
T(2,1)=T(0,0)=1.

When r=3, we have R(r)=2^(ceil(3/2))=4 entries in sequence 3. So, R(r)/2=2. The terms in row 3 are dependent only on row 2 and row 1.
1 1  ...(r=1)
2 1  ...(r=2)
1 2 1 1 ...(r=3)
Let us verify the pattern may be obtained using the derived equations.
Observe that for 0<=c<2 (entries in first half of sequence),
when r=3,c=0, r+c is odd, [#3] is applicable:
 T(3,0)=T(2,0)-T(1,0)=2-1=1
when r=3,c=1, r+c is even, [#1] is applicable:
 T(3,1)=T(2,1)+T(1,1)=1+1=2
For entries in the second half of the sequence, we only care which row they are in. In this instance, r=3 is odd, so [#2] is applied.
Observe that for 2<=c<4,
when c=2, the complicated looking index "c-(R(r)/2)" evaluates to 2-(4/2)=0, we have
T(r,c)=T(r-2,c-(R(r)/2))   
or T(3,2)=T(0,0)=1.
when c=3, c-(R(r)/2) evaluates to 3-(4/2)=1, we have
T(3,2)=T(0,1)=1.

When r=4, we have R(r)=4 elements in sequence 4. So, R(r)/2=2. Let's look at sequence 2 and 3.
2 1
1 2 1 1
3 1 1 2 <= sequence 4 will be checked

For 0<=c<2,
when r=4,c=0, r+c is even, applying [#1] is straight-forward:
T(4,0)=T(3,0)+T(2,0)=1+2=3
when r=4,c=1, r+c is odd, we apply [#3] instead:
T(4,1)=T(3,1)-T(2,1)=2-1=1 (so far so good, these entries agree with the pattern above)

For 2<=c<4,
we are only concern with the row index, since even, we apply [#4] to find entries in the second half of the sequence:

when c=2, the complicated looking index R(r-2)-1-[c-(R(r)/2))] evaluates to (2-1)-[2-(4/2)]=1, we have
T(r,c)=T(r-2,R(r-2)-1-[c-(R(r)/2)])
T(4,1)=T(2,1)=1.
when c=3, R(r-2)-1-[c-(R(r)/2))] evaluates to (2-1)-[3-(4/2)]=0, we have
T(4,1)=T(2,0)=2.

[Note carefully that we are copying from the back of sequence 2, from right to left as we populate the entries T(4,2) and T(4,3).]

When r=5, focus on row 3 and 4
1 2 1 1  ...r=3
3 1 1 2  ...r=4
for 0<=c<4
when c=0, r+c is odd -- we apply [#3]:
T(5,0)=T(4,0)-T(3,0)=2
when c=1, r+c is even -- we apply [#1]:
T(5,1)=T(4,1)+T(3,1)=1+2=3
similarly,
T(5,2)=T(4,2)-T(3,2)=0
T(5,3)=T(4,3)+T(3,3)=2+1=3

for 4<=c<8
we have
T(5,4)=T(3,0)=1
T(5,5)=T(3,1)=2
T(5,6)=T(3,2)=1
T(5,7)=T(3,3)=1

{2 3 0 3 1 2 1 1}

Reflection:

Q: Is this correct?
A: We can't say, but this "particular" (not necessarily unique) solution can be justified and agrees with the observed pattern.

Remark:
This type of question is quite meaningless in my opinion. It can be bent in many ways to produce the "desired" outcome. You can justify your assumptions in many ways. This type of question is a brain-tease, there is little to be gained after solving the problem. Not one that I can recommend to students.