Proof of Properties of the Falling Factorial

Throughout, $(n)_{k}=F(n,k)$ for the map $F$ of Existence and Uniqueness of the Falling Factorials (i) (The Falling Factorial (i)), so that

$$(n)_{0}=1,\qquad(0)_{k+1}=0,\qquad(n+1)_{k+1}=(n+1)\,(n)_{k};$$

$\binom{n}{k}=C(n,k)$ for the map $C$ of Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (i) (The Binomial Coefficient (i)); and products in $\mathbb{N}_{0}$ are rearranged by associativity and commutativity (Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (v), Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (vi)).

Step 1: falling factorials and binomial coefficients ((ii)). We prove, by induction on $n$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (viii)), that $(n)_{k}=k!\binom{n}{k}$ for every $k\in\mathbb{N}_{0}$. For $k=0$ both sides are $1$ at every $n$: $(n)_{0}=1$, and $0!\binom{n}{0}=1\cdot1=1$ by The Factorial: Recursion, Positivity and Bounds by Powers (i), Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (i) and Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (iii). It remains to treat $k+1$.

Base $n=0$. Since $0\le k$, we have $0<k+1$ (The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor (iv)), so $\binom{0}{k+1}=0$ (Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (ii)). Both sides vanish: $(0)_{k+1}=0$ and $(k+1)!\cdot0=0$ (Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (i)).

Induction step. Assume the claim for $n$ and all $k$. By the recursion, the induction hypothesis, absorption $(n+1)\binom{n}{k}=(k+1)\binom{n+1}{k+1}$ (Binomial Identities (iii)) and $(k+1)!=(k+1)\cdot k!$ (The Factorial: Recursion, Positivity and Bounds by Powers (i)),

$$(n+1)_{k+1}=(n+1)\,(n)_{k}=k!\,(n+1)\binom{n}{k}=k!\,(k+1)\binom{n+1}{k+1}=(k+1)!\binom{n+1}{k+1}.$$

Step 2: the diagonal value ((i)). Taking $k=n$ in (ii) and using $\binom{n}{n}=1$ (Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (iii)) and Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (iii),

$$(n)_{n}=n!\binom{n}{n}=n!.$$

Step 3: vanishing ((iii)). If $k>n$, then $\binom{n}{k}=0$ (Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (ii)), so by (ii) and Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (i),

$$(n)_{k}=k!\cdot0=0.$$

Step 4: positivity ((iv)). Let $k\le n$. Since $n!\ge1$ (The Factorial: Recursion, Positivity and Bounds by Powers (ii)), the factorial formula

$$k!\,(n-k)!\binom{n}{k}=n!$$

(Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (v)) gives $\binom{n}{k}\neq0$ (Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (i)). As $k!\ge1$ as well, (ii) gives $(n)_{k}=k!\binom{n}{k}\neq0$ (Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (vii)), so $(n)_{k}\ge1$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (v)).