Where do I start to create a computationally efficient algorithm for the problem below

Question

I have an upside down pyramid, e.g.

4          9          34          12
     -5         -25          22
           20          -47
                 67

where each element in a row is the difference between the two values above it.

If I am only given the final number (67 in this example), the number of levels in the pyramid (4 in this example), and the sum of all the values in the first row (59), how can I write an algorithm or function that can give me the first row of values?

Which mathematics domain that deals with this type of problems? Has this type of problem been solved before? If it is not possible to determine the first row of number if only given those 3 values (e.g. if there are more than one possibilities for the first row), how else can I design the problem so that I can determine the unique, original first row of numbers (e.g. maybe performing alternating addition and subtraction operations on the first row instead of just addition and giving that answer as the third given value instead of the sum)?

Answer 1

I think that linear algebra would do.

If you call the elements one the first row (you know they are four) $a_0, a_1, a_2, a_3$

the final number is $a_0 - 3 a_1 +3 a_2 -a_3 = 67$. Note that the coefficients are binomial coefficients.

The sum of all the values on the first row is $a_0 + a_1 + a_2 + a_3 = 59$.

Note that you have two equations and four unknowns. From here, you may be able to decide which other constraints you want to apply so that you can determine the unique, original first row of numbers.

Answer 2

The field is finite differences.

I don't think that the answer would be unique. The value in the $n$-th row (starting at $0$), if the values in the $0$-th row are $(a_k)_{k=0}^n$, would be $\sum_{k=0}^n (-1)^{k}\binom{n}{k}a_k $ and there are many ways the $a_k$ could be chosen to get a particular sum.