Stirling Number of n with n-m is Polynomial in n of Degree 2m/Unsigned First Kind

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $m \in \Z_{\ge 0}$.

The unsigned Stirling number of the first kind $\ds {n \brack n - m}$ is a polynomial in $n$ of degree $2 m$.


Proof

The proof proceeds by induction over $m$.

For all $m \in \Z_{\ge 0}$, let $\map P n$ be the proposition:

$\ds {n \brack n - m}$ is a polynomial in $n$ of degree $2 m$.


Basis for the Induction

$\map P 0$ is the case:

$\ds {n \brack n} = 1$

which is a polynomial in $n$ of degree $0$

Thus $\map P 0$ is seen to hold.


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that, if $\map P k$ is true, where $k \ge 0$, then it logically follows that $\map P {k + 1}$ is true.


So this is the induction hypothesis:

$\ds {n \brack n - k}$ is a polynomial in $n$ of degree $2 k$.


from which it is to be shown that:

$\ds {n \brack n - \paren {k + 1} }$ is a polynomial in $n$ of degree $2 \paren {k + 1}$.


Induction Step

This is the induction step:

Let $\map f {n, d}$ denote an arbitrary polynomial in $n$ of degree $d$.


Then:

\(\ds {n \brack n - \paren {k + 1} }\) \(=\) \(\ds {n \brack n - k - 1}\)
\(\ds \) \(=\) \(\ds \paren {n - 1} {n - 1 \brack n - k - 1} + {n - 1 \brack n - k - 2}\) Definition 1 of Unsigned Stirling Number of the First Kind
\(\ds \) \(=\) \(\ds \paren {n - 1} {n - 1 \brack \paren {n - 1} - k} + {n - 1 \brack \paren {n - 1} - \paren {k + 1} }\)


This needs considerable tedious hard slog to complete it.
In particular: This doesn't look promising
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Finish}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\ds {n \brack n - m}$ is a polynomial in $n$ of degree $2 m$.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Stirling_Number_of_n_with_n-m_is_Polynomial_in_n_of_Degree_2m/Unsigned_First_Kind&oldid=524826"