Task

Provide code that produces a list of numbers which is the   nth  order forward difference, given a non-negative integer (specifying the order) and a list of numbers.



The first-order forward difference of a list of numbers   A   is a new list   B,   where   Bn = An+1 - An.

List   B   should have one fewer element as a result.

The second-order forward difference of   A   will be:

tdefmodule Diff do
	def forward(arr,i\\1) do
		forward(arr,[],i)
	end

	def forward([_|[]],diffs,i) do
		if i == 1 do
			IO.inspect diffs
		else 
			forward(diffs,[],i-1)
		end
	end

	def forward([val1|[val2|vals]],diffs,i) do
		forward([val2|vals],diffs++[val2-val1],i) 
	end
end 

The same as the first-order forward difference of   B.

That new list will have two fewer elements than   A   and one less than   B.

The goal of this task is to repeat this process up to the desired order.

For a more formal description, see the related   Mathworld article.



Algorithmic options

 Iterate through all previous forward differences and re-calculate a new array each time.
 Use this formula (from Wikipedia):


 




Δ

n


[
f
]
(
x
)
=

∑

k
=
0


n





(


n
k


)



(
−
1

)

n
−
k


f
(
x
+
k
)


{\displaystyle \Delta ^{n}[f](x)=\sum _{k=0}^{n}{n \choose k}(-1)^{n-k}f(x+k)}




 (Pascal's Triangle   may be useful for this option.)


 
/* Forward differences. */ /* 23 April 2010 */
differences: procedure options (main);
   declare a(10) fixed(10) static initial
      (7, 3, 9, 250, 300, 4, 68, 72, 154, 601);
   declare (i, j, m, n, t, u) fixed binary;
 
   m = hbound(a,1);
   get (n); if n > m then signal error;
   put skip edit (a) (F(7));
   do i = 1 to n;
      t = a(i);
      do j = i+1 to m;
         u = a(j);
         a(j) = a(j) - t;
         t = u;
      end;
      put skip edit (a) (F(7));
   end;
   put skip edit ((a(i) do i = n+1 to m)) (F(9));
 
end differences;
 