Talk:Binomial transform

Involution

Hi Linas. Good luck with you edit. Note that the term self-conjugate is unknown to WP. The proper term is involution. Bo Jacoby 23:01, 28 January 2006 (UTC)

Thanks. If you are good at terminology, what is the name for a matrix/operator B when it has the property that MB=M. I keep wanting to say its "in the kernel of M", or "M kills B" or "its nilpotent", or "B a homomorphism of the kernel of M" but none of these, except for the last, are the right term. Any idea? linas 00:36, 31 January 2006 (UTC)

No, but what is M ? It is obviously not invertible unless B=1. If BB=B then B is idempotent. If MB=0 then B is in the kernel of M. If BB=0 then B is nilpotent. I'm a little confused about your new concept. Bo Jacoby 04:50, 31 January 2006 (UTC)

Oh, in this example, M is the Hankel transform, and B is the binomial transform. Think of these two transforms not as transforms, but as inf-dimensional matrices. Applying the binomial transform and more generally the k-binomial transform to a series leaves the Hankel transform of that series invariant. Clearly, M has a kernel, and B twists the kernel around. In the finest tradition of invariants in mathematics, whenever one has a kernel, one should mod by it, and so I am also wondering how to best describe the cosets of M modulo B, and/or make other interesting conclusions about it. linas 05:57, 31 January 2006 (UTC)

Polynomial extrapolation

If a_n is a polynomial in n, then s_n is finally zero. So you can extend a vector (like 1,4,9) by transforming into (1,-3,1), extending with zeroes: (1,-3,1,0,0,0), and transforming again: (1,4,9,16,25,36). This is polynomial extrapolation.

Transform
 1   4   9
-3  -5
 2
Extend and transform
 1  -3   2   0   0   0
 4  -5   2   0   0
 9  -7   2   0
16  -9   2
25 -11
36

Bo Jacoby 16:58, 30 January 2006 (UTC)

Huh. Never heard of polynomial extrapolation. linas 00:36, 31

January 2006 (UTC) Then see Extrapolation. Bo Jacoby 04:35, 31 January 2006 (UTC)

Oh. Duhh. OK, you just mean "use finite differences to fit a polynomial to the data"; yes, that is a cute trick. I didn't recognize it in the form you presented it in above; I'm reminded again that Newton must've been very smart, because the things he did would leave me scratching my head. I'll add a brief note to article on extrapolation. linas 05:15, 31 January 2006 (UTC)

Done. The article on finite differences should also be modified to bring in some of the theory from Newton series, which should be expanded. In fact, I just added the section on Newton series a few days ago, its pretty thin. linas 05:26, 31 January 2006 (UTC)

Note that binomial transformation is done without using multiplication or division, but only subtraction. You do not really need a computer to do it, but it helps. It is a cute way of computing square numbers: just start with three sequential square numbers, such as (1,0,1), and extend. So the squares are computed without multiplication! For polynomials of integer arguments the binomial transform is the natural set of coefficients. If the polynomial values are integers, then so are these coefficients, and vice versa. Bo Jacoby 07:52, 31 January 2006 (UTC)

Notation

I notice that you just introduced the Ta notation. This is fine in one or two places, but I find it to be cumbersome and daunting, and can impede understanding for newcomers. As a type of notation, it is good to mention and define, but it shouldn't get over-used. linas 16:07, 31 January 2006 (UTC)

OK. But a definition should define what it claims to define. Defining a transformation should give that transformation a name, say T, and place that name on the left hand side of an equality sign. Then the right hand side should contain a defining expression . Bo Jacoby 21:41, 31 January 2006 (UTC)

Temper. One need not use formulas and equals signs for everything; there have been great 20th century mathematicians who expressed themselves quite well without writing down a single equals sign (or arrow, or barely even a formula). I find that the best way to explain something is to present the same thing using two or three different notations for it, as well as a verbal description. No great matter, thanks for the edit; I may tweak it later.

I am reminded that I recently sat through an hour-long lecture on Wilson loops that didn't have any formulas in it. Although I failed to comprehend most of it, I did develop a marvelous intuitive understanding of a few things that were ... "obvious", when stated by the mouth of a good speaker. linas 03:56, 1 February 2006 (UTC)

Surely. A great article tells the reader what the concept is and what it is does and why it is worth while learning. Dedekinds title, Was sind und was sollen die Zahlen?, (Numbers, what are they and what shall they do?), is right to the point. The binomial transformation is fun for a child, but that fact does not yet show in the article. Hilbert wrote: immer mit den einfachsten Beispielen anfangen (always start with the simplest examples). I'm regret that I know nothing about Wilson loops, and I don't understand the article. Nor do I understand gauge theory. Please improve those articles. Bo Jacoby 08:40, 1 February 2006 (UTC)

I undid a lot of the new notation, for two reasons. I found the mapsto notation throughly opaque and confusing. Perhaps this should have its own article, instead of being folded into this one. I also undid the "Ta" notation, because it left the rest of the article hanging: the rest of the article assumed the earlier setup, and was rendered insensible because the setup had been removed.linas 20:52, 12 February 2006 (UTC)

Also, you called the transform T. Is this the standard name for this? Do you have any references for this? I vaguely remember seeing it called script-B i.e. ${\mathcal {B}}$. I don't have the Knuth reference, what does Knuth call it? I'd rather not invent a new notation, if it can be avoided. linas 20:59, 12 February 2006 (UTC)

Inverse sequence not unique?

Is there some extra condition needed for the pair of sequences $a_{n}$, $b_{n}$ to be unique inverses of each other? Because it seems that this sequence is not unique.

Let $a_{n}=n$, then both $b_{k}=-\delta _{1k}$ and $b_{k}=n2^{n-k}$ satisfy the inverse relation. But I think only the former is the correct forward transform of $a_{k}$. —The preceding unsigned comment was added by 154.20.149.5 (talk) 09:09, 8 January 2007 (UTC).

No sir, no extra condition is needed. Let $a_{n}=n$ be the sequence a = 0,1,2,3,4,5,... Write it as the first row of a table:

0  1  2  3  4  5 

The next row is computed by subtracting the neighbour to the right from each element in the first row

 0  1  2  3  4  5 
-1 -1 -1 -1 -1 

and so on:

 0  1  2  3  4  5 
-1 -1 -1 -1 -1 
 0  0  0  0 
 0  0  0
 0  0
 0

The first column produced is the transform b = 0,-1,0,0,0,0,... Now transform b in the same way to get the following table

 0 -1  0  0  0  0
 1 -1  0  0  0
 2 -1  0  0
 3 -1  0 
 4 -1
 5

The first column produced is the original sequence 0,1,2,3,4,5,... So each of the two sequences is the transform of the other. Bo Jacoby 20:44, 25 July 2007 (UTC).

Explicite multiplication signs help

This article are hard de decipher for the beginner because two variables without anything in between have several meanings: The formula

$(Ta)_{n}=\sum _{k=0}^{\infty }T_{nk}a_{k}$

might be written

$(Ta)_{n}=\sum _{k=0}^{\infty }T_{n,k}\cdot a_{k}$

to explain where it means multiplication as in

$\ T_{nk}a_{k}$

and where it means separator as in

$\ _{nk}$

and where it means function value as in

$\ Ta$.

Bo Jacoby 20:16, 25 July 2007 (UTC).

Euler transform not clear

The section should be self-contained. There is no explanation what ${\Delta ^{n}a_{0}}$ is.--84.189.98.228 (talk) 13:36, 28 October 2009 (UTC)

Example wrong?

Isn't the example wrong? I certainly don not get the same answer if I use either of the definitions given in the text. —Preceding unsigned comment added by MathHisSci (talk • contribs) 20:55, 15 September 2010 (UTC)

Nothing wrong with the example, the problem was with me as could be expected. MathHisSci (talk) 10:03, 8 November 2010 (UTC)

Regarding the example with the table of difference I don't think it is very clear. If one were to apply the binomial transform as s(n) = Sum(n=0 to n) (-1)^k (n k) a(k) then the sequence [0, 1, 10, 63, ...] is not the binomial transform of [0, 1, 8, 36, ...] but the other way round. I understand that the definition of binomial transform in terms of the difference table is that it takes the sequence of the leftmost diagonal to that of the 1st row, which is here given by s(n) = Sum(n=0 to n) (n k) a(k) but don't you think that this could be the source of extreme frustration for the beginner who is trying to make sense of it all? It can easily be made clearer, I think. Ciferhead (talk) 23:16, 6 August 2011 (UTC)

Main Formula

I see this page hasn't been edited for a while. The main formula appears to contain a typo. (-1) should be to the power n-k. A clue perhaps is in the fact that the inverse has the same formula, although that appears to be correct. See for instance Wolfram. SamCardioNgo (talk)

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

Just not sure if I'm missing something SamCardioNgo (talk) (date supposedly 22:22, 8 October 2015 (UTC))