One of my favorite facts from combinatorics is that $\sum\limits_{0\leq k\leq n}\binom{n}{k} = 2^{n}$. To prove it is simple: Note that $2 = 1 + 1$, and that $\binom{n}{k} = \binom{n}{k}\cdot 1^{k}\cdot 1^{n-k}$, and appeal to binomial theorem:
$$\sum_{0\leq k\leq n}\binom{n}{k} = \sum_{0\leq k\leq n}\binom{n}{k}\cdot 1^{n-k}\cdot 1^{k} = \left(1+1\right)^{n} = 2^{n}.$$
But what can we say about $\sum\limits_{1\leq k\leq n}k\binom{n}{k}$, or maybe even more general binomial coefficient sums?
For each real number $t>1$, one can define a probability distribution $P_{t} = \left\{\mathrm{pr}_{t}\left(n\right)\right\}_{n\in\mathbb{N}}$ by $\mathrm{pr}_{t}\left(n\right) = \displaystyle{\frac{n^{-t}}{\zeta\left(t\right)}}$. This class of probability functions was studied by Golomb in [1]. In this post, we will prove a theorem about relatively $r$-prime $s$-tuples of integers.
This problem was studied for the case $r = 1$ by Nymann in Example 2 of Section 2 of [2].
I was recently introduced to an interesting polynomial problem.
Problem. Determine all polynomials $p\left(x\right)\in \mathbb{R}\left[x\right]$ such that $\left(x – 16\right)p\left(2x\right) = 16\left(x – 1\right)p\left(x\right)$ for all $x\in \mathbb{R}$.
While reading some course notes from MIT 18.703 (Modern Algebra), I came across the following statement on page 3:
Lemma 22.3. The product of all primes $r$ between $N$ and $2N$ is greater than $2^{N}$.
However, this can quickly be shown false for $N = 8$.
So I had a question: “How many more counterexamples are there?”
Continue reading
Recall that the harmonic series $\displaystyle{\sum_{n=1}^{\infty}\frac{1}{n}}$ diverges.
This is because we may bound the partial sums below, like so:
$$1+\frac{1}{2}+\left(\frac{1}{3}+\frac{1}{4}\right)+\left(\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}\right)+\cdots >$$ $$\frac{1}{2}+\frac{1}{2}+\left(\frac{1}{4}+\frac{1}{4}\right)+\left(\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}\right)+\cdots=$$ $$\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\cdots\to\infty$$
We may replace $n$ by $an+b$, where $a,b\in\mathbb{R}$, $a$ and $b$ not both $0$, to retain a divergent sum, which we will prove below.
In an earlier post, titled A Fun Integral Problem, I gave a calculation for an integral as an infinite sum $\sum_{n=1}^{\infty}\frac{1}{n^{2}}$. I’ve been told that I should generalize it, so I’ll do that here (hence the title). I will also show how one may calculate some of the particular values of the Riemann $\zeta$ function we will be getting from this generalization, thus making good on my promise to give the value of that sum.
Problem. Calculate the integral
\[
\int_{\left[0,1\right]^{k}}\frac{dx_{1}\cdots dx_{k}}{1-x_{1}\cdots x_{k}}.
\]
Stop here if you want to try to use that previous post to solve this generalization. Continue reading for the solution as well as the actual values of the integrals for various values of $k$.
In two papers of Nymann and Leahey from the mid-to-late 70’s, they determined the asymptotics of the probabilities of selecting $k$ relatively prime integers [1] and selecting an integer which is $k$-free [2] according to the uniform and binomial distributions. I thought it would be a fun exercise to combine the results in the obvious way, extending their results in the binomial distribution while also coming up with an alternative proof of Benkoski’s result for the uniform distribution [3].
Continue reading
Yesterday, I was made aware of an elementary combinatorics problem, and the solution was surprisingly clever (at least it is to me, though I am not an expert in the area).
Suppose that a philanthropist decides to give a total of ten dollars in one-dollar bills to 3 people. How many ways can we distribute the money, assuming that we don’t have to do so evenly?
Continue reading
I saw this post on Reddit and was quite interested in it. I decided to investigate things on my own for a bit. We’ll start with the statement of the Cauchy Condensation Test.
Continue reading
This post is a rewritten (and slightly extended) form of a survey paper that I wrote in 2014 for a seminar as a graduate student. Proofs for many of the results have been omitted as they are available in their respective papers, listed in the references at the end of this post. I will, however, list proofs that make important points (such as the proof of the Sierpiński-Mazurkiewicz Paradox which doesn’t use the Axiom of Choice) or were not given in the original source (as is the case for a lemma in the first paper of Sherman).
Continue reading
