There is a number $n \in \mathbb{N}, \ n > 1, n < 2^k$. How to prove this statement:
$n$ is included into Pascal triangle not more than $2k -2$ times?
$\begingroup$
$\endgroup$
7
-
2$\begingroup$ Where does this question come from? $\endgroup$– Igor RivinCommented Dec 30, 2017 at 17:55
-
3$\begingroup$ From the way you phrase your question, you seem to know that this is a true statement. Where does that knowledge come from? $\endgroup$– André HenriquesCommented Dec 30, 2017 at 17:58
-
3$\begingroup$ In addition to the problems with lack of context, this question is cross-posted to MSE. $\endgroup$– Steven LandsburgCommented Dec 30, 2017 at 18:09
-
$\begingroup$ similar question: mathoverflow.net/questions/28717/singmasters-conjecture $\endgroup$– Pietro MajerCommented Dec 30, 2017 at 18:14
-
1$\begingroup$ Since the question appears to be an open research problem, I am not sure why this was closed. Voting to reopen. $\endgroup$– Igor RivinCommented Dec 30, 2017 at 19:44
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
4
This is a result of Singmaster (American Math Monthly, 1971).
Here is his proof ($N(a)$ is the number of times $a$ appears.) This result has since been much improved, see the wikipedia article on Singmaster's conjecture.
To elaborate somewhat, Abbott-Erdos-Hanson show:
and use this to show the better asymptotic bound. It is not quite clear how to use this to get better bounds for all $t.$
answered Dec 30, 2017 at 18:05
-
$\begingroup$ The proof gives $N(a)\le2+2\log_2a$, and OP wants $N(a)\le2k-2$ when $a<2^k$, which is a little bit stronger (but maybe the improved results in the wikipedia essay give what's needed). $\endgroup$ Commented Dec 30, 2017 at 19:14
-
$\begingroup$ @GerryMyerson The results in the wikipedia link are asymptotically better, so they definitely do the trick. I did not notice the plus vs minus, mea culpa. $\endgroup$ Commented Dec 30, 2017 at 19:21
-
$\begingroup$ if they're asymptotically better, then they do the trick for $a$ sufficiently large, but not necessarily for all $a$, right? $\endgroup$ Commented Dec 30, 2017 at 19:24
-
2$\begingroup$ @GerryMyerson See the edit. It is not clear that one can get the better result for ALL $t$ using this technology. $\endgroup$ Commented Dec 30, 2017 at 19:38