User:Steinmacher-Burow/sandbox

The Triangle of Binomial Transform Coefficients is like Pascal's Triangle.

This section introduces the triangle of binomial transform coefficients. The BTC triangle is like Pascal's triangle. The two triangles have the same rows and elements and values, except that all elements of Pascal's triangle are positive, while some particular elements of the BTC triangle are negative. The entry in the nth row and kth column of Pascal's triangle is ${\tbinom {n}{k}}$ for any non-negative integer n and any integer k between 0 and n. The binomial transform, T, of a sequence of values {v_n}, is the sequence {s_n} defined by

$s_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}v_{k}.$

Ignoring the sign term $(-1)^{k}$, the $n+1$ coefficients of the element s_n are the respective $n+1$ elements of the row n of Pascal's Triangle. The entry in the nth row and kth column of the BTC triangle is $(-1)^{k}{\tbinom {n}{k}}$ for any non-negative integer n and any integer k between 0 and n. This results in the following example rows $n=0$ through $n=7$, top to bottom, for the BTC triangle:

                             1                                  // Row n = 0.
                         1      -1                              // Row n = 1 or d = 0.
                     1      -2       1                          // Row n = 2 or d = 1.
                 1      -3       3      -1                      // Row n = 3 or d = 2.
             1      -4       6      -4       1                  // Row n = 4 or d = 3.
         1      -5      10     -10       5      -1              // Row n = 5 or d = 4.
     1      -6      15     -20      15      -6       1          // Row n = 6 or d = 5.
 1      -7      21     -35      35     -21       7      -1      // Row n = 7 or d = 6.

For Pascal's triangle and the BTC triangle, the entries in each row are numbered from the left beginning with $k=0$ and are staggered relative to the numbers in the adjacent rows, so that an element in a row has a left element and a right element in an adjacent row. As described at the top of this article, each element of each row n of Pascal's triangle is the result of the right element plus the left element in the adjacent row $n-1$, treating a blank right or left entry as 0. In contrast, each element of each row n of the BTC triangle is the result of the right element minus the left element in the adjacent row $n-1$, again treating a blank right or left entry as 0.

As described above, the elements in Pascal's triangle are the coefficients arising in binomial expansions. The numbers on row n of Pascal's triangle are the coefficients a_i in the expansion

$(x+1)^{n}=\sum _{i=0}^{n}a_{i}x^{i}.$

Similarly, the numbers on row n of the BTC triangle are the coefficients a_i in the expansion

$(x-1)^{n}=\sum _{i=0}^{n}a_{i}x^{i}.$

The binomial transform has a relationship to polynomials. The binomial transform of a sequence {v_n} is the nth forward differences of the sequence {v_n}, with odd differences carrying a negative sign, namely:

$s_{0}=v_{0}$

$s_{1}=-(\Delta v)_{0}=-v_{1}+v_{0}$

$s_{2}=(\Delta ^{2}v)_{0}=-(-v_{2}+v_{1})+(-v_{1}+v_{0})=v_{2}-2v_{1}+v_{0}$

$\vdots \,$

$s_{n}=(-1)^{n}(\Delta ^{n}v)_{0}$

where Δ is the forward difference operator. According to the method of finite differences, for any polynomial of degree d or less, any sequence of $d+2$ values at equally spaced positions has a $(d+1)$th difference exactly equal to 0. The element s_d+1 of the binomial transform is such a $(d+1)$th difference. For convenience, each row n of the above example BTC triangle also has a label $d=n-1$. Thus for any polynomial of degree d or less, any sequence of $d+2$values at equally spaced positions has a linear combination result of 0, when using the $d+2$ elements of row d of the BTC triangle as the corresponding linear coefficients. The points and values may be integer or real or complex values. The history of this result and related results are surveyed . For example, if $f(t)=c_{0}+c_{1}t+\cdots +c_{m}t^{m}$ is a polynomial of degree m, then the result is the $m<n$ case in entry (Z.8) of H. W. Gould's Combinatorial Identities which says

$\sum _{k=0}^{n}(-1)^{k}{n \choose k}f(k)={\begin{cases}0&{\mbox{if }}m<n,\\(-1)^{n}n!c_{n}&{\mbox{if }}m=n.\\\end{cases}}$

In appropriate scenarios, a row of the BTC triangle provides the linear coefficients to do polynomial interpolation as a linear combination of the given values.

With increasing d, the elements of row d and higher of the BTC triangle obey additional properties given by the polynomials of degree d. For the polynomial f(x) = 1 of degree 0, any sequence of $d+2$ values at equally spaced positions has a linear combination result of 0, when using the $d+2$ elements of row d as the corresponding linear coefficients. Each value in any such sequence is 1, so in each row of the BTC triangle, the sum of the elements is 0. For example in each row $d=1$ or higher, the coefficients have a linear combination result of 0 using the sequence $(1,2,3,...)$ from the polynomial $f(x)=x$, as demonstrated for row $d=3$, where $1*1+-4*2+6*3+-4*4+1*5=0$. For example in each row $d=2$ or higher, the coefficients have a linear combination result of 0 using the sequence $(1,4,9,...)$ from the polynomial $f(x)=x^{2}$, as demonstrated for row $d=3$, where $1*1+-4*4+6*9+-4*16+1*25=0.$

For a polynomial $f(x)$ of degree d, any sequence of $d+2$ values at equally spaced positions has a linear combination result of 0, when using the $d+2$ elements of row d as the corresponding linear coefficients. This also holds for a polynomial $g(x)$ of degree d, constructed to yield the same sequence of $d+2$values, but in reverse order. So in each row of the BTC triangle, the element values are symmetric front to back. On reversing a row with even d, the overall difference in sign does not impact the linear combination result of 0.

---- CUT ---------- add below aft Definition on Polynomial interpolation

A Linear Combination of the Given Values

The Lagrange form of the interpolating polynomial is a linear combination of the given values. In many scenarios, an efficient and convenient polynomial interpolation is a linear combination of the given values, using previously known coefficients. Given a set of $k+1$ data points

$(x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{k},y_{k})$

where each data point is a (position, value) pair and where no two positions $x_{j}$ are the same, the interpolation polynomial in the Lagrange form is a linear combination

$y(x):=\sum _{j=0}^{k}y_{j}c_{j}(x)$

of the given values $y_{j}$ with each coefficient $c_{j}(x)$ given by evaluating the corresponding Lagrange basis polynomial using the given $k+1$ positions $x_{j}$.

$c_{j}(x)=\ell _{j}(x,x_{0},x_{1},\ldots ,x_{k}):=\prod _{\begin{smallmatrix}0\leq m\leq k\\m\neq j\end{smallmatrix}}{\frac {x-x_{m}}{x_{j}-x_{m}}}={\frac {(x-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x-x_{j-1})}{(x_{j}-x_{j-1})}}{\frac {(x-x_{j+1})}{(x_{j}-x_{j+1})}}\cdots {\frac {(x-x_{k})}{(x_{j}-x_{k})}}.$

Each coefficient $c_{j}(x)$ in the linear combination depends on the given positions $x_{j}$ and the desired position $x$, but not on the given values $y_{j}$. For each coefficient, inserting the values of the given positions $x_{j}$ and simplifying yields an expression $c_{j}(x)$, which depends only on $x$. Thus the same coefficient expressions $c_{j}(x)$ can be used in a polynomial interpolation of a given second set of $k+1$ data points

$(x_{0},v_{0}),\ldots ,(x_{j},v_{j}),\ldots ,(x_{k},v_{k})$

at the same given positions $x_{j}$, where the second given values $v_{j}$ differ from the first given values $y_{j}$. Using the same coefficient expressions $c_{j}(x)$ as for the first set of data points, the interpolation polynomial of the second set of data points is the linear combination

$v(x):=\sum _{j=0}^{k}v_{j}c_{j}(x).$

For each coefficient $c_{j}(x)$ in the linear combination, the expression resulting from the Lagrange basis polynomial $\ell _{j}(x,x_{0},x_{1},\ldots ,x_{k})$ only depends on the relative spaces between the given positions, not on the individual value of any position. Thus the same coefficient expressions $c_{j}(x)$ can be used in a polynomial interpolation of a given third set of $k+1$ data points

$(t_{0},w_{0}),\ldots ,(t_{j},w_{j}),\ldots ,(t_{k},w_{k})$

where each position $t_{j}$ is related to the corresponding position $x_{j}$ in the first set by $t_{i}=a*x_{i}+b$ and the desired positions are related by $t=a*x+b$, for a constant scaling factor a and a constant shift b for all positions. Using the same coefficient expressions $c_{j}(t)$ as for the first set of data points, the interpolation polynomial of the third set of data points is the linear combination

$w(t):=\sum _{j=0}^{k}w_{j}c_{j}(t).$

In many applications of polynomial interpolation, the given set of $k+1$ data points is at equally spaced positions. In this case, it can be convenient to define the x-axis of the positions such that $x_{i}=i$. For example, a given set of 3 equally-spaced data points $(x_{0},y_{0}),(x_{1},y_{1}),(x_{2},y_{2})$ is then $(0,y_{0}),(1,y_{1}),(2,y_{2})$. The interpolation polynomial in the Lagrange form is the linear combination

${\begin{aligned}y(x):=\sum _{j=0}^{2}y_{j}c_{j}(x)=y_{0}{\frac {(x-1)(x-2)}{(0-1)(0-2)}}+y_{1}{\frac {(x-0)(x-2)}{(1-0)(1-2)}}+y_{2}{\frac {(x-0)(x-1)}{(2-0)(2-1)}}\\=y_{0}{\frac {(x-1)(x-2)}{2}}+y_{1}{\frac {(x-0)(x-2)}{-1}}+y_{2}{\frac {(x-0)(x-1)}{2}}.\end{aligned}}$

This quadratic interpolation is valid for any position x, near or far from the given positions. So, given 3 equally-spaced data points at $x=0,1,2$ defining a quadratic polynomial, at an example desired position $x=1.5$, the interpolated value after simplification is given by

$y(1.5)=y_{1.5}=(-y_{0}+6y_{1}+3y_{2})/8$

This is a quadratic interpolation typically used in the Multigrid method.

Again given 3 equally-spaced data points at $x=0,1,2$ defining a quadratic polynomial, at the next equally spaced position $x=3$, the interpolated value after simplification is given by

$y(3)=y_{3}=y_{0}-3y_{1}+3y_{2}$

In the above polynomial interpolations using a linear combination of the given values, the coefficients were determined using the Lagrange method. In some scenarios, the coefficients can be more easily determined using other methods. Examples follow.

According to the method of finite differences, for any polynomial of degree d or less, any sequence of $d+2$ values at equally spaced positions has a $(d+1)$th difference exactly equal to 0. The element s_d+1 of the Binomial transform is such a $(d+1)$th difference. The binomial transform, T, of a sequence of values {v_n}, is the sequence {s_n} defined by

$s_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}v_{k}.$

Ignoring the sign term $(-1)^{k}$, the $n+1$ coefficients of the element s_n are the respective $n+1$ elements of the row n of Pascal's Triangle. The triangle of binomial transform coefficients is like Pascal's triangle. The entry in the nth row and kth column of the BTC triangle is $(-1)^{k}{\tbinom {n}{k}}$ for any non-negative integer n and any integer k between 0 and n. This results in the following example rows n = 0 through n = 7, top to bottom, for the BTC triangle:

                             1                                  // Row n = 0.
                         1      -1                              // Row n = 1 or d = 0.
                     1      -2       1                          // Row n = 2 or d = 1.
                 1      -3       3      -1                      // Row n = 3 or d = 2.
             1      -4       6      -4       1                  // Row n = 4 or d = 3.
         1      -5      10     -10       5      -1              // Row n = 5 or d = 4.
     1      -6      15     -20      15      -6       1          // Row n = 6 or d = 5.
 1      -7      21     -35      35     -21       7      -1      // Row n = 7 or d = 6.

For convenience, each row n of the above example BTC triangle also has a label $d=n-1$. Thus for any polynomial of degree d or less, any sequence of $d+2$ values at equally spaced positions has a linear combination result of 0, when using the $d+2$ elements of row d as the corresponding linear coefficients.

For example, 4 equally spaced data points of a quadratic polynomial obey the linear equation given by row $d=2$ of the BTC triangle.

$0=y_{0}-3y_{1}+3y_{2}-y_{3}$

This is the same linear equation as obtained above using the Lagrange method.

The BTC triangle can also be used to derive other polynomial interpolations. For example, the above quadratic interpolation

$y(1.5)=y_{1.5}=(-y_{0}+6y_{1}+3y_{2})/8$

can be derived in 3 simple steps as follows. The equally spaced points of a quadratic polynomial obey the rows of the BTC triangle with $d=2$ or higher. First, the row $d=3$ spans the given and desired data points $y_{0},y_{1},y_{1.5},y_{2}$ with the linear equation

$0=1y_{0}-4y_{0.5}+6y_{1}-4y_{1.5}+1y_{2}$

Second, the unwanted data point $y_{0.5}$ is replaced by an expression in terms of wanted data points. The row $d=2$ provides a linear equation with a term $1y_{0.5}$, which results in a term $4y_{0.5}$ by multiplying the linear equation by 4.

$0=1y_{0.5}-3y_{1}+3y_{1.5}-1y_{2}=4y_{0.5}-12y_{1}+12y_{1.5}-4y_{2}$

Third, the above two linear equations are added to yield a linear equation equivalent to the above quadratic interpolation for $y_{1.5}$.

$0=(1+0)y_{0}+(-4+4)y_{0.5}+(6-12)y_{1}+(-4+12)y_{1.5}+(1-4)y_{2}=y_{0}-6y_{1}+8y_{1.5}-3y_{2}$

Similar to other uses of linear equations, the above derivation scales and adds vectors of coefficients. In polynomial interpolation as a linear combination of values, the elements of a vector correspond to a contiguous sequence of regularly spaced positions. The p non-zero elements of a vector are the p coefficients in a linear equation obeyed by any sequence of p data points from any degree d polynomial on any regularly spaced grid, where d is noted by the subscript of the vector. For any vector of coefficients, the subscript obeys $d\leq p-2$. When adding vectors with various subscript values, the lowest subscript applies for the resulting vector. So, starting with the vector of row $d=3$ and the vector of row $d=2$ of the BTC triangle, the above quadratic interpolation for $y_{1.5}$ is derived by the vector calculation

$(1,-4,6,-4,1)_{3}+4*(0,1,-3,3,-1)_{2}=(1,0,-6,+8,-3)_{2}$

Similarly, the cubic interpolation typical in the Multigrid method,

$y_{1.5}=(-y_{0}+9y_{1}+9y_{2}-y_{3})/16,$

can be derived by a vector calculation starting with the vector of row $d=5$ and the vector of row $d=3$ of the BTC triangle.

$(1,-6,15,-20,15,-6,1)_{5}+6*(0,1,-4,6,-4,1,0)_{3}=(1,0,-9,16,-9,0,1)_{3}$

---- CUT ---------- add below to Constant-recursive sequence

Sequence of values from any polynomial on a regularly-spaced grid

For each value $d\geq 1$, the corresponding row of the triangle of binomial transform coefficients provides the d coefficients $c_{i}$ for an order-d homogeneous linear recurrence with constant coefficients. The first few equations are listed below.

s(n) = 1s(n-1)                                 // Recurrence order d=1 obeyed by any 0th order polynomial.
s(n) = 2s(n-1) - 1s(n-2)                       // Recurrence order d=2 obeyed by any 1st order polynomial.
s(n) = 3s(n-1) - 3s(n-2) + 1s(n-3)             // Recurrence order d=3 obeyed by any 2nd order polynomial.
s(n) = 4s(n-1) - 6s(n-2) + 4s(n-3) - 1s(n-4)   // Recurrence order d=4 obeyed by any 3rd order polynomial.

Any given sequence of d values $s(0),s(1),\dots ,s(d-1)$ can be used to define a polynomial of degree $d-1$, where the values are assumed to be at contiguous positions on a regularly spaced grid. The d values may be integers or reals or complex numbers. Using the appropriate above order-d homogeneous linear recurrence, the given sequence of d values also defines and is part of a constant recursive sequence. The constant recursive sequence is the sequence of values from that polynomial on a regularly-spaced grid. For example, given the 2 values $s(0)=15,s(1)=25$ defining a polynomial of degree 1, then the above equation for $d=2$ yields the next value of the polynomial as

$s(2)=2s(1)-1s(0)=2*25-15=35$

and same above equation for $d=2$ yields the next value as

$s(3)=2s(2)-1s(1)=2*35-25=45$

Each above equation for recurrence order d is obeyed by any polynomial of order $d-1$ or less. So, the same result for $s(3)$ is also obtained by using the above equation for $d=3$.

$s(3)=3s(2)-3s(1)+1s(0)=3*35-3*25+15=45$

yields the same result the next value is

Any given sequence of d values $s(0),s(1),\dots ,s(d-1)$ contiguous on a regularly spaced grid defines a polynomial of degree $d-1$. The given sequence of d values also defines and is part of a constant recursive sequence, is the first on a

>> BEGIN OLD TEXT

An order-d homogeneous linear recurrence with constant coefficients is an equation of the form

$s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\cdots +c_{d}s(n-d),$

where the d coefficients $c_{1},c_{2},\dots ,c_{d}$ are constants.

A sequence $s(0),s(1),s(2),\dots$ is a constant-recursive sequence if there is an order-d homogeneous linear recurrence with constant coefficients that it satisfies for all $n\geq d$.

Equivalently, $s(n)_{n\geq 0}$ is constant-recursive if the set of sequences

$\{s(n+r)_{n\geq 0}:r\geq 0\}$

is contained in a vector space whose dimension is finite.

Fibonacci sequence

The sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... of Fibonacci numbers satisfies the recurrence

with initial conditions

Explicitly, the recurrence yields the values

etc.

>> END OLD TEXT

---- CUT ---------- add below to Extrapolation#Polynomial

In some scenarios, a polynomial interpolation or extrapolation is simply a (TODO link: linear combination of the known values).

---- CUT ---------- add below to Interpolation#Polynomial interpolation

In some scenarios, calculating the polynomial interpolation is computationally inexpensive, since the polynomial interpolation is a linear combination of the known values.

However, polynomial interpolation also has some disadvantages. Polynomial interpolation may exhibit oscillatory artifacts, especially at the end points (see Runge's phenomenon). Furthermore in some scenarios, calculating the interpolating polynomial is computationally expensive (see computational complexity) compared to linear interpolation.

OLD TEXT: However, polynomial interpolation also has some disadvantages. Calculating the interpolating polynomial is computationally expensive (see computational complexity) compared to linear interpolation. Furthermore, polynomial interpolation may exhibit oscillatory artifacts, especially at the end points (see Runge's phenomenon).

---- CUT ---------- add below to bottom of Linear prediction

For equally-spaced values, polynomial interpolation is a linear combination of the known values. If the discrete time signal is estimated to obey a polynomial of degree $p-1,$ then the predictor coefficients $a_{i}$ are given by the corresponding row of the triangle of binomial transform coefficients. This estimate might be suitable for a slowly varying signal with low noise. The predictions for the first few values of p are

${\begin{array}{lcl}p=1&:&{\widehat {x}}(n)=1x(n-1)\\p=2&:&{\widehat {x}}(n)=2x(n-1)-1x(n-2)\\p=3&:&{\widehat {x}}(n)=3x(n-1)-3x(n-2)+1x(n-3)\\p=4&:&{\widehat {x}}(n)=4x(n-1)-6x(n-2)+4x(n-3)-1x(n-4)\\\end{array}}$

======EXCEPT FOOTNOTES, DELETE BELOW ============================================

DELETE BELOW

The pattern produced by an elementary cellular automaton using rule 60 is exactly Pascal's triangle of binomial coefficients reduced modulo 2 (black cells correspond to odd binomial coefficients). Rule 102 also produces this pattern when trailing zeros are omitted. Rule 90 produces the same pattern but with an empty cell separating each entry in the rows.