I'm intrigued by this claim:

''Every number-theoretic function $f(n)$ can be written in the form $$f(n)=\sum_i c_i{n\choose i}$$ for certain (positive, negative, or zero) integer coefficients $c_i$. The $c_i$ are called the Stirling coefficients of $f$.''

made in Myhill, 'Equivalence Types and Combinatorial Functions' in Nagel, Suppes and Tarski (eds) 'Logic, Methodology and Philosophy of Science, proceedings of the 1960 International Congress', Stanford UP, 1962. The quotation is on page 49.

Is a ''number-theoretic function'' simply a function $f:\mathbb N\to\mathbb Z$? If so, I'd like to know how the claim is proved. Surely there are uncountably many functions $f:\mathbb N\to\mathbb Z$ but only countably many functions $f(n)=\sum_i c_i{n\choose i}$?

Most likely I've misunderstood it completely.

Myhill goes on to define a combinatorial function as being one of the displayed form with all the $c_i$ being non-negative. He then says ''they include all polynomials with non-negative integer coefficients, and a good many with some negative or rational non-integer coefficients.'' Since the $c_i$ are integers, how can the coefficients be negative or non-integral?

  • 2
    $\begingroup$ There are uncountably many functions of that form: each $c_i$ can be any integer. $\endgroup$ – Angina Seng Jun 27 '19 at 17:34
  • 3
    $\begingroup$ It seems easy to prove by construction. First choose $c_1$ by setting $n = 1$, then $c_2$, ... etc. $\endgroup$ – Jakobian Jun 27 '19 at 17:37
  • $\begingroup$ My puzzlement continues and I've added my next problem to my post. My apologies if I'm just being thick. $\endgroup$ – Justin Jun 27 '19 at 17:51
  • 2
    $\begingroup$ ${n\choose2}=\frac{n^2-n}2$ is a polynomial with non-integer coefficients. $\endgroup$ – Angina Seng Jun 27 '19 at 18:19
  • $\begingroup$ @Lord Shark the Unknown thank you. Clearly I am just being thick. $\endgroup$ – Justin Jun 27 '19 at 18:31

(Almost) every function $f : \mathbb R \to \mathbb R$ can be developed into a Newton's series $$ f(x) = \sum\limits_k {\Delta ^{\,k} f(0)\binom{x}{k}\;} $$

If then it is also $f : \mathbb N \to \mathbb Z$ , the finite differences are integral.

Therefore I do not get exactly the point of your question.

  • $\begingroup$ @G Cab Nor I! My question was based on a severe misunderstanding. Thank you for drawing my attention to Newton's series. $\endgroup$ – Justin Jul 12 '19 at 12:29
  • $\begingroup$ @Justin: glad to help in putting the matter on the right track. $\endgroup$ – G Cab Jul 12 '19 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.