Friday, 11 July 2014

exponentiation - Expressing Factorials with Binomial Coefficients



Expression



I have somehow stumbled upon this expression (I believe I have proved it, but that is not important right now), which I have tried to simplify by writing it like something like this (I have been playing with powers of natural numbers and something similar to Pascal's triangle) :




n! = (t-1)^n , t^a=(a+1)^n



n is a natural number; and t^a is used to replace powers of t's in (t-1)^n with natural numbers to the power of n. (Not to be used as direct equalities!)




For example, take 5 for n:



5! = (t-1)^5




5! = t^5 - 5 * t^4 + 10 * t^3 - 10 * t^2 + 5 * t^1 - 1



5! = 6^5 - 5 * 5^5 + 10 * 4^5 - 10 * 3^5 + 5 * 2^5 - 1



5! = 120



120 = 120



This is true for any natural number n.




Questions






Firstly, is there a similar or exact expression or formula out there already declared and explained with all of its properties, and if yes what is, where is it, and is it useful in any way?






Mainly, are there and what are other more convenient ways to express or write this down, maybe even simplify?




UPDATE: @abiessu Thanks, for your answer to this part.



UPDATE: @abiessu and @DanielFischer♦ Thanks, for correcting my expression of notation.






And lastly, if you wish, how would you prove such an expression with most elegance?



UPDATE: @abiessu Thanks, for your answer to this part.







UPDATES:



The comments will for sure give you a better idea of what I'm look for and hoping to find.




Use $$ n!=(n+1)^n-nn^n+\binom n2(n-1)^n-\dots $$ instead to look at the expression in its better notation easier to understand I believe.




Answer



Note that $k^m$ can be written as a linear combination of $\binom{k}{j}$ for $j$ from $0$ to $m$. If fact, this is what the Stirling Numbers of the Second Kind are perfect for:
$$
\newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}}
k^m=\sum_{j=0}^mj!\stirtwo{m}{j}\binom{k}{j}\tag{1}
$$
Using $(1)$ and other binomial identities, we get
$$
\begin{align}
\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k+1)^n

&=\sum_{k=0}^n(-1)^k\binom{n}{k}\sum_{i=0}^n(-1)^i\binom{n}{i}(n+1)^{n-i}k^i\tag{2}\\
&=\sum_{k=0}^n(-1)^k\binom{n}{k}\sum_{i=0}^n(-1)^i\binom{n}{i}(n+1)^{n-i}\sum_{j=0}^ij!\stirtwo{i}{j}\binom{k}{j}\tag{3}\\
&=\sum_{i=0}^n\sum_{j=0}^i(-1)^i\binom{n}{i}(n+1)^{n-i}j!\stirtwo{i}{j}\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{k}{j}\tag{4}\\
&=\sum_{i=0}^n\sum_{j=0}^i(-1)^i\binom{n}{i}(n+1)^{n-i}j!\stirtwo{i}{j}\sum_{k=0}^n(-1)^k\binom{n}{j}\binom{n-j}{k-j}\tag{5}\\
&=\sum_{i=0}^n\sum_{j=0}^i(-1)^i\binom{n}{i}(n+1)^{n-i}j!\stirtwo{i}{j}(-1)^n[j=n]\tag{6}\\
&=(-1)^n\binom{n}{n}(n+1)^{n-n}n!\stirtwo{n}{n}(-1)^n\tag{7}\\[9pt]
&=n!\tag{8}
\end{align}
$$
Explanation:
$(2)$: apply the Binomial Theorem to $(n-k+1)^n$
$(3)$: apply $(1)$ to $k^i$
$(4)$: rearrange factors
$(5)$: $\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$
$(6)$: $\sum_{k=0}^n(-1)^k\binom{n-j}{k-j}=(1-1)^{n-j}$ which is $1$ only if $n=j$ and $0$ otherwise
$(7)$: if $j=n$, then $i=n$
$(8)$: evaluate



No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...