Lagrange's Zero-One Blocks (LZOB)

Lagrange's Zero-One Blocks (LZOB) is somewhat a sub-part of Lagrange Interpolation which especially aims at constructing a general formula of a certain sequence on basis of known few terms of that sequence.

Constructing a formula for any sequence of numbers. This technique was developed by a great mathematician-astronomer, Joseph Louis Lagrange.

No matter how many first consecutive terms of a sequence are given , they do not force on us any specific pattern. It is always possible to use a suitable number of zero-one blocks and construct a formula which will agree with the first given \(k\) terms and the next term of sequence can be assigned any number of our choice.

As an explicit example , suppose the sequence is \(2,5,10,17\) , then what is the next term? If you go by seeking pattern you would find that the differences are \(3,5,7\) between the two consecutive terms. So , you would get the next term as \(17+9=\boxed{26}\) . But what if you want next term as \(1729\)? or \(\sqrt{\pi}\)? This is where LZOB proves useful. With the help of LZOB , we can assign any number as the next term in the sequence , in fact we can find a general formula for sequence! So let's find it!

We have to find general formula for the sequence \(2,5,10,17\) such that

• If you put \(n=1\) in the formula , it will give you \(a_1=2\)

• If you put \(n=2\) in the formula , it will give you \(a_2=5\)

• If you put \(n=3\) in the formula , it will give you \(a_3=10\)

• If you put \(n=4\) in the formula , it will give you \(a_4=17\)

• If you put \(n=5\) in the formula , it will give you \(a_5=1729\)

First let us define \(B_1(n)=\dfrac{(n-2)(n-3)(n-4)(n-5)}{(1-2)(1-3)(1-4)(1-5)}\)

Note: When we define \(B_k(n)\) , we exclude \((n-k)\) term in the numerator and the terms in the denominator are of the form \((k-m)\) where \(m\neq k\) .

Now we shall compute \(B_1(n)\) for \(n=1,2,3,4,5\).

Indeed , \(B_1(2)=B_1(3)=B_1(4)=B_1(5)=0\) because if we put either \(n=2\) or \(3\) or \(4\) or \(5\) , the numerator is anyway going to be equal to zero. Now what about \(B_1(1)\)?

If you put \(n=1\) , we see that the numerator does look the same as the denominator and we have \(B_1(1)=1\) .

So we have \(\boxed{B_1(1)=1 \ , \ B_1(2)=B_1(3)=B_1(4)=B_1(5)=0}\).

Do you see now , why is \(B_1(n)\) called a 'zero-one' block?

Now we move on to compute second block , that is \(B_2(n)=\dfrac{(n-1)(n-3)(n-4)(n-5)}{(2-1)(2-3)(2-4)(2-5)}\)

Following the same method as done for first block , we have \(\boxed{B_2(2)=1 \ , \ B_2(1)=B_2(3)=B_2(4)=B_2(5)=0}\).

Similarly , \(B_3(n)=\dfrac{(n-1)(n-2)(n-4)(n-5)}{(3-1)(3-2)(3-4)(3-5)}\)

\(\boxed{B_3(3)=1 \ , \ B_3(1)=B_3(2)=B_3(4)=B_3(5)=0}\)

Similarly , \(B_4(n)=\dfrac{(n-1)(n-2)(n-3)(n-5)}{(4-1)(4-2)(4-3)(4-5)}\)

\(\boxed{B_4(4)=1 \ , \ B_4(1)=B_4(2)=B_4(3)=B_4(5)=0}\)

Similarly , \(B_5(n)=\dfrac{(n-1)(n-2)(n-3)(n-4)}{(5-1)(5-2)(5-3)(5-4)}\)

\(\boxed{B_5(5)=1 \ , \ B_5(1)=B_5(2)=B_5(3)=B_5(4)=0}\)

Since we want the fifth term \(a_5=1729\) , we make 5 blocks.

Now we are ready to construct a formula for \(a_n\). Indeed the formula is :

\[\boxed{a_n=B_1(n)a_1 + B_2(n)a_2 + B_3(n)a_3 + B_4(n)a_4+B_5(n)a_5}\]

You may compute \(a_1,a_2,a_3,a_4,a_5\) to confirm the above claim.

Suppose you are given first \(k\) terms of sequence \(<a_i>\) and we need to find the formula for \(n^{th}\) term in the sequence.

• Since \(k\) terms are given of sequence , we need to make \(k\) zero-one blocks.

• Each block is in the form \(\large{B_i(n)=\frac{\displaystyle\prod_{j=1}^k (n-j)}{(n-i)\displaystyle\prod_{j=1 \ , \ j\neq i}^k (i-j)}}\) where \(1\leq i,j \leq k\) .

• For every block \(B_i(i) = 1\) and all other \(B_i(j)=0\).

• Now we have general formula for nth term in sequence as:

\[\Large \boxed{a_n=\displaystyle\sum_{i=1}^k B_i(n)a_i}\]