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}$$