User:Nathan L. Skirrow/useful polynomiality

this is mostly intended as a small reference page for myself, but also a complete derivation because (though all is well-known) none of the StackExchange answers or papers I've seen seem to explain it very thoroughly

conventions

herein, we use ${\underline {\%}}$ in the manner of programming languages; $p{\underline {\%}}q=p-\left\lfloor {\frac {p}{q}}\right\rfloor q$ and $p{\overline {\%}}q=p-\left(\left\lceil {\frac {p}{q}}\right\rceil -1\right)q={\begin{cases}q&p{\underline {\%}}q=0\\p{\underline {\%}}q&\mathrm {else} \end{cases}}$. Like how $\left\lceil {\frac {p}{q}}\right\rceil =\left\lfloor {\frac {p-1}{q}}\right\rfloor +1$, we have $p{\overline {\%}}q=(p-1){\underline {\%}}q+1$

as per usual, let $x^{\underline {n}}={\frac {x!}{(x-n)!}}$ and $x^{\overline {n}}={\frac {(x+n-1)!}{(x-1)!}}$.

quadratics

$\mathrm {root} (ax^{2}-2bx+c)={\frac {b}{a}}\pm {\sqrt {\left({\frac {b}{a}}\right)^{2}-{\frac {c}{a}}}}$

since $\cos(2\mathrm {acos} (x))=2x^{2}-1$, one can choose $y=x-{\frac {b}{a}}$ to make it $ay^{2}+c-{\frac {b^{2}}{a}}$, then $z={\frac {y}{\sqrt {2\left({\frac {b^{2}}{a^{2}}}-{\frac {c}{a}}\right)}}}$ for $(2z^{2}-1)\left({\frac {b^{2}}{a}}-c\right)$, so $ax^{2}-2bx+c=\left({\frac {b^{2}}{a}}-c\right)\cos \left(2\mathrm {acos} \left({\frac {ax-b}{\sqrt {2\left(b^{2}-ac\right)}}}\right)\right)$, and in particular $\mathrm {root} (ax^{2}-2bx+c)={\frac {b}{a}}\left(1\pm {\sqrt {2}}\cos \left({\frac {\mathrm {acos} \left({\frac {-ac}{b^{2}}}\right)}{2}}\right)\right)$

cubics

$\cos(3\mathrm {acos} (x))=\cosh(3\mathrm {acosh} (x))=4x^{3}-3x$, so given $ax^{3}+bx^{2}+cx+d$, one can choose $y=x+{\frac {b}{3a}}$ to get $ay^{3}+\left(c-{\frac {b^{2}}{3a}}\right)y={\frac {bc}{3a}}-{\frac {2b^{3}}{27a^{2}}}-d$, then $z={\frac {3a}{2{\sqrt {b^{2}-3ac}}}}y$ to change the left side to ${\frac {2(b^{2}-3ac)^{\frac {3}{2}}}{27a^{2}}}(4z^{3}-3z)$, so $\mathrm {root} (ax^{3}+bx^{2}+cx+d)={\frac {2{\sqrt {b^{2}-3ac}}}{3a}}\cos \left({\frac {\mathrm {acos} \left({\frac {9abc-2b^{3}-27a^{2}d}{2(b^{2}-3ac)^{\frac {3}{2}}}}\right)+2\pi n}{3}}\right)-{\frac {b}{3a}}$

Gauss's multiplication formula (factorial splitting)

define the $k$-multifactorial $n!^{(k)}=\prod _{j=1}^{n}j^{[j\equiv n\ (\mathrm {mod} \ k)]}=\prod _{j=0}^{\left\lceil {\frac {n}{k}}\right\rceil -1}n-jk$, then (since $n!=n(n-1)!$ holds everywhere) we have $n!^{(k)}=(n/k)^{\underline {\lceil n/k\rceil }}k^{\lceil n/k\rceil }={\frac {(n/k)!}{(n/k-\lceil n/k\rceil )!}}k^{\lceil n/k\rceil }={\frac {(n/k)!}{(n/k{\overline {\%}}1-1)!}}k^{\lceil n/k\rceil }$.

We also have $n!=\prod _{i=0}^{k-1}(n-i)!^{(k)}$, so we can put the multifactorial-as-factorial-fraction formula inside the factorial-as-multifactorial-product!

${\begin{aligned}&(kn)!\\=&\prod _{i=0}^{k-1}(kn-i)!^{(k)}\\=&\prod _{i=0}^{k-1}(n-i/k)^{\underline {n}}k^{n}\\=&k^{kn}\prod _{i=0}^{k-1}{\frac {(n-i/k)!}{(-i/k)!}}\\=&k^{kn}\prod _{i=0}^{k-1}\left(1-{\frac {i}{k}}\right)^{\overline {n}}\end{aligned}}$

since it holds for all $n$, we can find the $n$-independent denominator exactly! (not relevant here)

by letting $n\rightarrow \infty$ in order for Stirling's approximation to become exact, and also using $n^{\underline {x}}{\underset {n}{\sim }}n^{x}$, ie. $\lim _{n\rightarrow \infty }{\frac {n!/(n-x)!}{n^{x}}}=1$

${\begin{aligned}\prod _{i=0}^{k-1}(-i/k)!&=\lim _{n\rightarrow \infty }{\frac {k^{kn}}{(kn)!}}\prod _{i=0}^{k-1}(n-i/k)!\\&=\lim _{n\rightarrow \infty }{\frac {k^{kn}n!^{k}}{(kn)!}}\prod _{i=0}^{k-1}{\frac {(n-i/k)!}{n!}}\\&=\lim _{n\rightarrow \infty }{\frac {k^{kn}n!^{k}}{(kn)!}}\prod _{i=0}^{k-1}n^{-i/k}\\&={\frac {k^{kn}{\sqrt {2\pi n}}^{k}\left({\frac {n}{e}}\right)^{kn}}{{\sqrt {2\pi kn}}\left({\frac {kn}{e}}\right)^{kn}}}n^{\frac {1-k}{2}}\\&={\sqrt {\frac {(2\pi )^{k-1}}{k}}}\end{aligned}}$

(see my page for applying this to integrals, with an interpretation of Stirling's approximation)

putting these together, we get

$(kn)!={\frac {k^{kn+{\frac {1}{2}}}}{{\sqrt {2\pi }}^{k-1}}}\prod _{i=0}^{k-1}\left(n-{\frac {i}{k}}\right)!$

and when offset,

$(kn+o)!=\prod _{i=0}^{k-1}(kn+o-i)!^{(k)}=k^{kn}\prod _{i=0}^{k-1}{\frac {\left(n+{\frac {o-i}{k}}\right)!}{\left({\frac {o-i}{k}}{\overline {\%}}1-1\right)!}}k^{[o>i]}={\frac {k^{kn+o}}{\prod _{i=0}^{k-1}\left({\frac {-i}{k}}\right)!}}\prod _{i=0}^{k-1}\left(n+{\frac {o-i}{k}}\right)!=o!k^{kn}\prod _{i=0}^{k-1}{\frac {\left(n+{\frac {o-i}{k}}\right)!}{\left({\frac {o-i}{k}}\right)!}}=o!k^{kn}\prod _{i=0}^{k-1}\left(1+{\frac {o-i}{k}}\right)^{\overline {n}}$

trinomials

let $f(x)=ax^{n}+bx=c$, then the Lagrange inversion theorem gives $f^{-1}(y)=\sum _{j=1}^{\infty }\left[{\frac {x^{j-1}}{(j-1)!}}\right]\left({\frac {x}{f(x)}}\right)^{j}{\frac {y^{j}}{j!}}$.

(note that Lagrange inversion's "$f$ must have nonzero derivative at $x=0$" criterion prevents us from giving the second term an arbitrary exponent $bx^{k}$)

In this case, for $j\equiv 1\ (\mathrm {mod} \ n-1)$, $\left[{\frac {x^{j-1}}{(j-1)!}}\right]\left({\frac {1}{b+ax^{n-1}}}\right)^{j}=b^{-j}\left[{\frac {x^{\frac {j-1}{n-1}}}{(j-1)!}}\right]{\frac {1}{\left(1+{\frac {a}{b}}x\right)^{j}}}=(j-1)!b^{-j}\left({\frac {-a}{b}}\right)^{\frac {j-1}{n-1}}{(j-1)\left(1+{\frac {1}{n-1}}\right) \choose j-1}=b^{-j}\left({\frac {-a}{b}}\right)^{\frac {j-1}{n-1}}{\frac {\left((j-1)\left(1+{\frac {1}{n-1}}\right)\right)!}{\left({\frac {j-1}{n-1}}\right)!}}$, so (substituting $j:=(n-1)j+1$)

$f^{-1}(y)=\sum _{j=0}^{\infty }{\frac {1}{b^{(n-1)j+1}}}\left({\frac {-a}{b}}\right)^{j}{\frac {(nj)!}{j!}}{\frac {y^{(n-1)j+1}}{((n-1)j+1)!}}={\frac {y}{b}}\sum _{j=0}^{\infty }{\frac {(nj)!}{((n-1)j+1)!}}{\frac {\left({\frac {-ay^{n-1}}{b^{n}}}\right)^{j}}{j!}}$

this also means

$(f^{-1})'(y)={\frac {1}{b}}\sum _{j=0}^{\infty }{nj \choose j}\left({\frac {-ay^{n-1}}{b^{n}}}\right)^{j}$

splitting the factorials,

${\begin{aligned}f^{-1}(y)&={\frac {y}{b}}\sum _{j=0}^{\infty }{\frac {n^{nj}\prod _{i=0}^{n-1}\left(1-{\frac {i}{n}}\right)^{\overline {j}}}{(n-1)^{(n-1)j}\prod _{i=0}^{n-2}\left({\frac {n-i}{n-1}}\right)^{\overline {j}}}}{\frac {\left({\frac {-ay^{n-1}}{b^{n}}}\right)^{j}}{j!}}\\&={\frac {y}{b}}\sum _{j=0}^{\infty }{\frac {\prod _{i=1}^{n-1}\left(1-{\frac {i}{n}}\right)^{\overline {j}}}{\left({\frac {n}{n-1}}\right)^{\overline {j}}\prod _{i=2}^{n-2}\left({\frac {n-i}{n-1}}\right)^{\overline {j}}}}{\frac {\left({\frac {-n^{n}a}{(n-1)^{n-1}b^{n}}}y^{n-1}\right)^{j}}{j!}}\\&={\frac {y}{b}}{_{n-1}F_{n-2}}\left({*\left({\frac {i}{n}},\right)_{i=1}^{n-1} \atop *\left({\frac {i}{n-1}},\right)_{i=2}^{n-2},{\frac {n}{n-1}}};{\frac {-n^{n}a}{(n-1)^{n-1}b^{n}}}y^{n-1}\right)\end{aligned}}$

the $n=2$ case is the only one which isn't reducible to a lower-degree hypergeometric, because the second member of the denominator Pochhammers which cancels the first numerator doesn't exist yet,

$\mathrm {root} (ax^{2}-2bx+c)={\frac {c}{2b}}{_{2}F_{1}}\left({{\frac {1}{2}},1 \atop 2};{\frac {ac}{b^{2}}}\right)$

and since we have $\cos(3\mathrm {acos} (x))=\cosh(3\mathrm {acosh} (x))=-\sin(3\mathrm {asin} (x))=4x^{3}-3x$ and $\sinh(3\mathrm {asinh} (x))=4x^{3}+3x$,

${\begin{aligned}\sin \left({\frac {\mathrm {asin} (y)}{3}}\right)&={\frac {y}{3}}{_{2}F_{1}}\left({{\frac {1}{3}},{\frac {2}{3}} \atop {\frac {3}{2}}};y^{2}\right)={\frac {1}{3}}\sum _{n=0}^{\infty }{3n \choose n}\left({\frac {2^{2}}{3^{3}}}\right)^{n}{\frac {y^{2n+1}}{2n+1}}\\\sinh \left({\frac {\mathrm {asinh} (y)}{3}}\right)&={\frac {y}{3}}{_{2}F_{1}}\left({{\frac {1}{3}},{\frac {2}{3}} \atop {\frac {3}{2}}};-y^{2}\right)\end{aligned}}$

another application is to determine the growth rate of the $n$-bonacci numbers, defined $F_{n}(k)={\begin{cases}0&k<n-1\\1&k=n-1\\\sum _{i=1}^{n}F_{n}(k-i)&k\geq n\end{cases}}$. Their o.g.f. is ${\frac {x^{n-1}}{1-x{\frac {1-x^{n}}{1-x}}}}={\frac {x^{n-1}(1-x)}{1-2x+x^{n+1}}}$, whose denominator's closest root (and only one within the unit circle) is the real one (the principal value that the hypergeom gets!),

$\lim _{k\rightarrow \infty }{\frac {F_{n}(k)}{F_{n}(k+1)}}=\mathrm {root} (2x-x^{n+1}=1)={\frac {1}{2}}{_{n}F_{n-1}}\left({*\left({\frac {i}{n+1}},\right)_{i=1}^{n} \atop *\left({\frac {i}{n}},\right)_{i=2}^{n-1},{\frac {n+1}{n}}};{\frac {(n+1)^{n+1}}{n^{n}2^{n+1}}}\right)$

with c₁=1, c₂=A094214, c₃=A192918; in particular, we can normalise the cubic and get

$A192918={\frac {17}{9}}{_{2}F_{1}}\left({{\frac {1}{3}},{\frac {2}{3}} \atop {\frac {1}{2}}};-{\frac {17^{2}}{2^{3}}}\right)-{\frac {1}{3}}={\frac {{\sqrt {8}}\sinh \left({\frac {\mathrm {asinh} \left({\frac {17}{\sqrt {8}}}\right)}{3}}\right)-1}{3}}$

external links

• M. Lawrence Glasser, 1994-11-16. The quadratic formula made hard: A less radical approach to solving equations (explains the same thing at a higher level)