`f`

will be denoted using `f'`

. The $\delta f: \mathbb R \rightarrow \mathbb R; (\delta f)(x) = f(x + 1) - f(x)$

Immediately, we can see that this operator is linear:
$\begin{aligned}
&\delta(f + g)
&= (f+g)(x+1) - (f+g)(x) \\
&= (f(x+1) - f(x)) + (g(x+1)-g(x)) \\
&= (\delta f) + (\delta g) \\
&\delta(\alpha f)(x)
&= (\alpha f)(x+1) - (\alpha f)(x) \\
&= \alpha \cdot (f(x+1) - f(x)) \\
&= \alpha (\delta f)
\end{aligned}$

it obeys a slightly corrupted version of the chain rule, $(fg)' = f' g + g' f$:
$\begin{aligned}
&\delta(fg) \\
&= (fg)(x+1) - (fg)(x) \\
&= f(x+1)g(x+1) - f(x)g(x) + 0 \\
&= f(x+1)g(x+1) - f(x)g(x) + [f(x)g(x+1) - f(x)g(x+1)] \\
&= g(x+1)[f(x+1) - f(x)] + f(x)[g(x+1) - g(x)] \\
&= g(x+1)(\delta f)(x) + f(x) (\delta g)(x) \\
&= (S \delta f)(x) + (f \delta g)(x) [(Sh)(x) \equiv h(x+1)] \\
&= (S \delta f + f \delta g)(x) \\
\end{aligned}$

We need this new $S$ operator to shift the function's input from $x$ to $x+1$.
$\delta(x^2) = (x+1)^2 - x^2 = 2x + 1$

This is disappointing, it does not behave very well `:(`

However, there $x^{(n)} \equiv x(x-1)(x-2)\cdots(x-n+1)$

For example:
$x^{(0)} = 1 \\
x^{(1)} = x \\
x^{(2)} = x(x-1) \\
x^{(3)} = x(x-1)(x-2) \\$

Let's try and apply our discrete difference $\delta$:
$\begin{aligned}
&\delta(x^{(2)}) \\
& = (x+1)(x-1+1) - x(x-1) \\
& = (x+1)(x) - x(x-1) \\
& = x*2 = 2x(1) \\
&\delta(x^{(3)}) \\
&= (x+1)(x-1+1)(x-2+1) - x(x-1)(x-2) \\
&= (x+1)(x)(x-1) - x(x-1)(x-2) \\
&= x(x-1)((x+1) - (x-2)) = 3x(x-1) = 3x^{(2)} \\
\end{aligned}$

These falling factorials look pretty unnatural though, why do we care?
Well, once we build some integral calculus, we can handle our problem
of $\sum_{1 \leq i < k} i^2$ using this calculus, by rewriting $i^2$
in terms of these falling factorials.
$\int_a^b f'(i) di = f(b) - f(a) \mapsto \sum_{a \leq i < b} (\delta f)(i) =?= f(b) - f(a)$

we can check if the assertion is true:
$\begin{aligned}
&\sum_{a \leq i < b} (\delta f)(i) \\
&= [f(a+1) - f(a)] + [f(a+2) - f(a+1)] + [f(a+3)-f(a+2)] + \cdots + [f(b) - f(b-1)] \\
&= f(b) - f(a) \quad \text{(The sum telescopes)}
\end{aligned}$

Sweet, so we just kicked a theory of calculus of the ground. Let's put
this to some use:
$\sum_{0 \leq i < n} i = \sum_{0 \leq i < n} i^{(1)} = i^{(2)}/2 \big|_{0}^n = n(n-1)/2$

Let's now derive the closed form form the sum of squares of $[1\cdot(k-1)]$:
$\begin{aligned}
&\sum_{0 \leq i < n} i^2 \\
&= \sum_{0 \leq i < n} i*(i-1) + i \\
&= \sum_{0 \leq i < n} i^{(2)} + i^{(1)} \\
&= n^{(3)}/2 + n^{(2)}/2 \\
&= n(n-1)(n-2)/3 + n(n-1)/2 \\
&= n(n-1)(n/3 - 2/3 + 1/2) \\
&= n(n-1)(2n - 1)/6 \\
\end{aligned}$

Trying to perform this process in general does beg a question: how do we
convert from $x^n$ into some combination of rising and falling factorials?
It turns out that $\begin{aligned}
&d'f(x) = f(x) | f(0) = 1 \\
&f(x+1) - f(x) = f(x) | f(0) = 1 \\
&f(x+1) = 2f(x) | f(0) = 1 \\
&f(n) = 2^n
\end{aligned}$

What does this buy us? It gives us a nice proof that $\sum_{k} nCk = 2^n$.
It proceeds by taking the taylor of $e^x$, "combinatorializing it", and then
simplifying:
$\begin{aligned}
&e^x = \sum_{n=0}^\infty \frac{x^n}{n!} \\
&2^x = \sum_{n=0}^\infty \frac{x^{(n)}}{n!} \\
& = \sum_{n=0}^\infty \frac{x*(x-1)*(x-2)*\cdots(x-n+1)}{n!} \\
& = \sum_{n=0}^\infty \frac{x*(x-1)*(x-2)*\cdots(x-n+1)}{n!}
\end{aligned}$

$x^{(n)} = x(x+1)(x+2) \dots (x+n-1) = \sum_{i=0}^n [n, i] x^i$

The question as a combinatorialist is:
what do the unsigned striling numbers of the first kind, $[n, i]$, count?The answer is:

$[n, i]$ counts the number of permutations of $n$ elements with $i$ disjoint cycles.There is a more evocative definition, which goes like this:

$[n, i]$ counts the number of ways to seat $n$ people at $i$ circular tables, such that no table is left empty.For example, in the case of the permutations of the set $\{1, 2, 3\}$, we have the permutations:

$\begin{aligned}
(1)(2)(3) \text{3 cycles} \\
(12)(3) \text{2 cycles} \\
(1)(23) \text{2 cycles} \\
(2)(13) \text{2 cycles} \\
(132) \text{1 cycle} \\
(123) \text{1 cycle} \\
\end{aligned}$

So, this gives the counts:
- $[3, 1] = 2$
- $[3, 2] = 3$
- $[3, 3] = 1$

- $[3, 1]$ is the number of ways to seat 3 people at 1 table. The firstperson sits at the table in only
**one way**. The second person can sit to theleft or to the right of the first person, but this is symmetric: they toohave only**one way**. Now the third person can sit to the left of the firstperson or to the left of the second person. So there are**two ways**.In total, there are only two ways.**Key idea:**On a circular table, itonly matters who is to your left, since there is no difference between leftand right.The second person has two choices: they - $[3, 3]$ is the number of ways to seat 3 people at 3 tables so that no tableis empty. We are forced to place one person per table.
- $[3, 2]$ is the number of ways to seat 3 people at 2 tables so that no tableis empty. So we will need to have two people on the first table,and then the final personal on the second table.Once we pick which two people sit together in the first table, we are done,because for upto two people, it doesn't matter how they sit at a table,the situation is symmetric.

$[n+1, k] = n[n, k] + [n, k-1]$

This can be seen combinatorially. If we want the number permutations of $n+1$ objects
with $k$ cycles, we can either:
- Take the permutations of $n$ objects with $k-1$ cycles, $[n, k-1]$, and theninsert the new $(n+1)$th object into a new cycle all by itself. That is,we create a new permutation where $p(n+1) = (n+1)$.
- Take the permutation of $n$ objects with $k$ cycles, and insert this new $(n+1)$thobject into any of the $k$ cycles. If the original permutation had
`x -p-> y`

,we can insert this new object as`x -p-> * -p->y`

for any`x`

. Thus, there are$n$ choices of locations to inser`*`

--- as the image of all possible`x`

s.This gives us the $n[n, k]$ term.

$\sum_{k=1}^n [n, k] = n!$