Generating function and finite difference.

Question

The above example is from Introduction to Combinatorial Analysis by John Riordan.

Here $\Delta$ is the difference operator.

But I am unable to understand why $\Delta 0^r = 1^r, \Delta^2 0^r = 2^r-2$ and $\Delta^3 0^r = 3^r - 3 \times 2^r +3$.

---

What I was trying is $\Delta 0^r = (0+1)^r - 0^r = 1^r$, but then $\Delta^2 0^r = \Delta 1^r = (1+1)^r - 1^r = 2^r - 1$, which is not matching with the book.

Answer 1

Riordan's notation is obscuring a lot, which makes things confusing. To make things clear, you need to understand that $\Delta$ operator takes in a sequence of numbers, and returns a new sequence of numbers. The notation $\Delta^2 0^r$, therefore, means the following, in plain English:

• Start with the sequence whose $i^\text{th}$ element is $i^r$. Let us call this sequence $s$.

• Apply $\Delta$ to this sequence, to get the sequence $\Delta(s)$, whose $i^\text{th}$ element is $(i+1)^r-i^r$.

• Apply $\Delta$ to the resulting sequence, to get $\Delta^2(s)$. The $i^\text{th}$ element of $\Delta^2(s)$ is $$ \underbrace{\Big(((i+1)+1)^r-(i+1)^r\Big)}_{(i+1)^\text{st}\text{ element of $\Delta(s)$}} -\underbrace{\Big((i+1)^r-i^r\Big)}_{i^\text{th}\text{ element of $\Delta(s)$}} =(i+2)^r-2(i+1)^r+i^r$$

• Finally, $\Delta^2 0^r$ really means "the zeroth element of the sequence $\Delta^2(s)$". Evaluating the above expression at $i=0$, the result is $2^r-2\cdot 1^r+0^r=2^r-2$.

The same logic allows you to find $\Delta^30^r=3^r-3\cdot 2^r+2\cdot 1^r-0^r$.

Answer 2

I am by no means an expert on the umbral calculus, but here is my guess at what Riordan had in mind.

Consider a forward difference table for the function $x^r$: $$\begin{array}{ccccccccc} \color{red}{0^r} & &1^r & & 2^r & & 3^r \\ & \color{red}{1^r} & & 2^r-1 & & 3^r-2^r \\ & & \color{red}{2^r-2} & & 3^r-2 \cdot 2^r+1 \\ & & & \color{red}{3^r - 3 \cdot 2^r + 3} \end{array}$$

The values Riordan gives for $\Delta 0^r$, $\Delta^2 0^r$ and $\Delta^3 0^r$ appear on the diagonal.

Answer 3

Here the difference operator $\Delta$ operates on functions and is defined by J. Riordan as \begin{align*} \color{blue}{\Delta f(n)=f(n+1)-f(n)}\tag{1} \end{align*} We obtain from (1) \begin{align*} \Delta f(n)&=f(n+1)-f(n)\\ \color{blue}{\Delta^2 f(n)}&=\Delta\left(f(n+1)-f(n)\right)\\ &=\Delta f(n+1)-\Delta f(n)\\ &=\left(f(n+2)-f(n+1)\right)-\left(f(n+1)-f(n)\right)\\ &\,\,\color{blue}{=f(n+2)-2f(n+1)+f(n)}\tag{2} \end{align*} We can represent the difference operator $\Delta$ using the shift operator $E$ with $E f(n)=f(n+1)$ and the identity operator $I$ with $I f(n)=f(n)$ as \begin{align*} \color{blue}{\Delta}&\color{blue}{=E-I}\\ \color{blue}{\Delta f(n)}&=f(n+1)-f(n)=Ef(n)-If(n)\color{blue}{=(E-I)f(n)} \end{align*} We can also derive (2) using shift and identity operator as \begin{align*} \color{blue}{\Delta^2 f(n)}&=\left(E-I\right)^2f(n)\\ &=\left(E^2-2E+I\right)f(n)\\ &=E^2f(n)-2Ef(n)+If(n)\\ &\,\,\color{blue}{=f(n+2)-2f(n+1)+f(n)}\tag{3} \end{align*} Now we consider the special case $f(n)=n^r$. We derive from (2) and (3) \begin{align*} \Delta^2 f(n)=\Delta^2 n^r=(n+2)^r-2(n+1)^r+n^r\tag{4} \end{align*} Evaluating (4) at $n=0$ we derive \begin{align*} \color{blue}{\Delta^2 0^r}=2^r-2\cdot 1^r+0^r\color{blue}{=2^r-2} \end{align*}

Similarly we obtain \begin{align*} \Delta^3 f(n)&=f(n+3)-3f(n+2)+3f(n+1)-f(n)\\ \Delta^3 n^r&=(n+3)^r-3(n+2)^r+3(n+1)^r-n^r\\ \color{blue}{\Delta^3 0^r}&=3^r-3\cdot 2^r+3\cdot 1^r-0^r\color{blue}{=3^r-3\cdot 2^r+3} \end{align*}

Note: As J. Riordan stated, is this notation common in difference calculus which is thoroughly treated in C. Jordan's classic Calculus of Finite Differences.