# Discrete math: create general formula

For any real number $x$ and positive integer $k$, define the notation [x,k] by the recursion $[x,k+1] = (x-k) [x,k]$ and $[x,1] = x$.

If n is any positive integer, one can now express the monomial $x^n$ as a polynomial in $[x,1], [x,2], . . . , [x,n]$. Find a general formula that accomplishes this, and prove that your formula is correct.

I am struggling finding the final formula.

I multiplied some of the polynomials out to get

$$x=[x,1]$$ $$x^2=[x,2]+[x,1]$$ $$x^3=[x,3]+3[x,2]+2[x,1]$$ $$x^4=[x,4]+6[x,3]+3[x,2]+4[x,1]$$

I am stumped where to go from here. I am unsure of how to create a formula from this, I feel like the trailing coefficients would be a factorial but am not sure if this is helpful in this scope.

-

Your term $[x,\ k]$ is just the falling factorial of $k$ steps $(x)_k = x(x-1)\cdots(x-k+1)$. This is just given by the Stirling numbers of the second kind in the generating function $$x^n = \sum_{k=1}^n\left\{\begin{matrix} n \\ k \end{matrix}\right\}(x)_k$$

In particular, your formula for $x^3$ and $x^4$ seem to be off by a bit.

The Stirling numbers of the second kind themselves are characterized by the recursion $$\left\{\begin{matrix} n+1 \\ k \end{matrix}\right\} = k\left\{\begin{matrix} n \\ k \end{matrix}\right\} + \left\{\begin{matrix} n \\ k-1 \end{matrix}\right\}$$ with the initial values $$\left\{\begin{matrix} 0 \\ 0 \end{matrix}\right\} = 1,\ \ \ \ \left\{\begin{matrix} n \\ 0 \end{matrix}\right\}=\left\{\begin{matrix} 0 \\ k \end{matrix}\right\}=0$$

Edit: Just out of general interest, I think I should mention one application of such a decomposition. If you are familiar with calculus, then you may notice that an integral is just a generalized telescoping sum (that's essentially the statement of the fundamental theorem of calculus).

The same methods can be generalized (or simplified depending on your point of view) for finite sums. This is a general branch of mathematics called Calculus of Finite Differences. Replacing the derivative is the forward difference operator $\Delta f(x) = f(x+1)-f(x)$, and the Fundamental Theorem of Finite Difference Calculus is just a telescoping sum $$f(x) = \sum_{k=0}^n\Delta f(n) = f(n+1)-f(0)$$ The falling factorial has significance in that $$\Delta (x)_n = n(x)_{n-1}$$ which is the equivalent of the power rule of calculus. Therefore if you can decompose a polynomial into falling factorials, you can applying the telescoping sum to the difference and find an easy closed form formula for the sum. This is one of the ways to find the sums of consecutive $n$th powers for example.

-
So my $x^3 term$ should be $[x,3]+3[x,2]+[x,1]$? – Nick Nov 2 '12 at 15:48
Seems that way, yes. – EuYu Nov 2 '12 at 15:54
I have $[x,2] = (x-1)x=> x^2-x$ and I sub that in to $[x,3]=(x-2)(x^2-x) => x^3-3x^2+2x$. Do you know what I am doing wrong to get that two at the end? – Nick Nov 2 '12 at 16:04
That two is fine. You have $$(x^3 - 3x^2 + 2x) + 3(x^2 - x) + x$$ for your final sum. – EuYu Nov 2 '12 at 16:07
ah! I see now. Thanks you're answer was very helpful. – Nick Nov 2 '12 at 16:08