2
$\begingroup$

In the following equation, $$n^s=(n)_s+f(s)$$ What is general form for $f(s)$? Understand that, $$(n)_s=n(n-1)(n-2)\cdots(n-[s-1])=\text{ The Falling Factorial }$$

I have experimented with this equation for $s=\{1,2,3,4\}$. Unless my calculations are horribly mangled, the following table arises: $$ \begin{array}{c|c} s & f(s)\\ \hline 1 & 0\\ 2 & n\\ 3 & 3n^2-2n\\ 4 & 6n^3-11n^2+6n \end{array} $$

I cannot see any reasonable pattern to these values. There isn't an obvious (to me) reccurence relationship, so that method of solving this seems useless. I would appreciate any help on this; it is a personal curiosity of mine. I'm a freshman in highschool. So, I would appreciate elaboration on any complex or complicated methods.

To be more specific, I would like $f(s)$ defined in the form of a polynomial. This is the particular form I was considering: $$f(s)=c_{s-1}n^{s-1}+c_{s-2}n^{s-2}+\dots+c_{1}n$$

  • 0
    Where did $q$ come from?2012-04-11
  • 0
    @ThomasAndrews Ah, drat. I checked the Wikipedia definition of the falling factorial and unwittingly wrote $q$ rather than $s$.2012-04-11
  • 0
    @ThomasAndrews, $c_{s-1}\neq 3 \text{ when } s=3$. Also, $c_1=-2 \text{ when } s=3$.2012-04-11
  • 0
    Whoops, got them reversed, $c_{s-1}=\frac{s(s-1)}2$ and $c_2=(s-1)!$.2012-04-11
  • 1
    @ThomasAndrews I think you have your indexing backwards - it's $c_1$ that's $(s-1)!$ and $c_{s-1}$ that's $s-1\choose 2$.2012-04-11

1 Answers 1

2

What you want are known as the Stirling numbers of the first kind; the unsigned version is generally denoted as $\displaystyle{s\brack i}$, and the cofefficients of your polynomial are given by $\displaystyle{f_s(n) = \sum_{i=0}^{s-1} (-1)^{s-i+1}{s\brack i}}n^i$. Note that I'm writing this as $f_s(n)$ rather than $f(s)$, since the latter suggests that it's a function of $s$ where it's more properly thought of as a sequence of functions indexed by $s$. There are recurrence formulas for the coefficients, but there's no explicit representation of them. For more details, I'd suggest checking out the Wikipedia page as a starting point; both of the book references in that article (Knuth's The Art Of Computer Programming and Knuth, Graham and Patashnik's Concrete Mathematics) are excellent sources for learning more about them.

  • 0
    "there's no explicit representation of them" Really? That's depressing. Is there any explanation for this? (I have _Concrete Mathematics_, but I have not read through it entirely.)2012-04-11
  • 0
    Also, this confirms your validity: http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind#Stirling_numbers_of_the_first_kind As such, I am accepting this answer. Thank you.2012-04-11
  • 0
    @user22144 I should be more careful in my phrasing; there are formulas for finding the numbers. In general, the lack of an explicit formula for this thing is to be expected - it's _having_ an explicit formula that's usually the pleasant surprise!2012-04-11
  • 0
    Ah, I understood what your phrasing meant. I was depressed because of the fact that it's usually elegant and beautiful to find the explicit formula. However, I suppose explicit formulae are much less common than I presumed. (And, for an explicit formula, this is quite terrifying: http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind#Explicit_formula )2012-04-11
  • 0
    In this case, I wouldn't be surprised if the lack of explicit formulas of certain kinds is actually related to some rather deep mathematics involving the factorial (and its generalization, the Gamma function), specifically Hölder's theorem that the Gamma function doesn't solve any algebraic differential equation.2012-04-11
  • 0
    If you are going to put the $\sum$ in, you should probably include the $n^i$.2012-04-11
  • 0
    @ThomasAndrews You have a good point. He should rephrase it to read, $$f_s(n)=\sum_{i=0}^{s-1}(-1)^{s-i+1}{s \brack i}n^{i}$$2012-04-11
  • 0
    Ayep, I missed that - thanks for the edit!2012-04-11