Tree addtion has to do with Pascal's Triangle, why?

46 Views Asked by At

Let me define tree addition of a list of numbers as follows:

4  3 2 1
 7  5 3
  12 8
   20

I conjecture that it is true that the tree addition of n numbers equals the numbers summed where each one gets its Tartaglia (Pascal) coefficient.

    1
   1 1
  1 2 1
 1 3 3 1

In the example above we got four numbers, so line four

1 3 3 1

We sum multipliying by the coefficents:

4*1 + 3*3 + 2*3 + 1*1 -> 4 + 9 + 6 + 1 -> 20

The same result as above. May my conjecture be true this holds true for all the tree additions of n numbers. Is it, if it is, why?

1

There are 1 best solutions below

0
On BEST ANSWER

One way of seeing what wowlolbrommer referred to in a (now deleted) comment is to write out each set of contribution paths as follows:

0   0   0   1
  0   0   1
    0   1
      1

and

0   0   1   0
  0   1   1
    1   2
      3

etc. and you can see how many paths goes trough each point and how many "copies" of the original number that enters the total at the bottom.