Challenge Math Challenge - September 2021

[fresh_42]

Summary: Gamma function. Combinatorics. Stochastic. Semisimple Modules. Topological Groups. Metric spaces. Logarithmic inequality. Stochastic. Primes. Approximation theory.1. (solved by @julian and @benorin ) Let $f$ be a function defined on $(0,\infty)$ such that $f(x)>0$ for all $x>0.$ Suppose that $f$ has the following properties:

1. $\log f(x)$ is a convex function.
2. $f(x+1)=x\cdot f(x)$ for all $x>0.$
3. $f(1)=1.$

Then $f(x)=\displaystyle{\lim_{n \to \infty}\dfrac{n!n^x}{x(x+1)\cdots (x+n)}}=:\Gamma(x)$ for all $x>0.$2. (solved by @TeethWhitener ) Let $T = (x_1, x_2, \ldots , x_m)$ be a sequence of not necessarily distinct reals. For any positive $b$, define
$$
T_b := \{(x_i, x_j ) \,|\, 1 \leq i, j \leq m, |x_i-x_j | \leq b\}.
$$
Show that for any sequence $T$ and for every integer $r>1,$
$$|T_r| < (2r-1)|T_1|.$$

3. (solved by @Office_Shredder ) Let $X,Y$ be two independent identically distributed real random variables. For a positive $b,$ define $p_b:=\operatorname{prob}\left(|X-Y|\leq b\right).$ Then for every integer $r,$ $p_r\leq (2r-1)p_1.$ Thus
$$
\operatorname{prob}\left(|X-Y|\leq 2\right) \leq 3\cdot \operatorname{prob}\left(|X-Y|\leq 1\right)
$$

4. Let $\mathbb{F}$ be a field and $G$ a finite group, such that $\operatorname{char}\mathbb{F}\,\nmid\,|G|.$ Prove that $\mathbb{F}G$ is semisimple, and show that this is not true if $\operatorname{char}\mathbb{F}\,\mid\,|G|.$5. A group $G$ together with a topology, such that the mapping on $G\times G$ (equipped with the product topology) to $G$ given by $(x,y)\longmapsto xy^{-1}$ is continuous, is called a topological group (e.g. a Lie group). Prove

1. (solved by @jbergman ) $G$ is a topological group if and only if inversion and multiplication are continuous.
2. (solved by @jbergman ) The mappings $x\longmapsto xg$ and $x\longmapsto gx$ are homeomorphisms for each $g\in G.$
3. (solved by @jbergman ) Each open subgroup $U\leq G$ is closed, and each closed subgroup $U\leq G$ of finite index is open. If $G$ is compact, then each open subgroup is of finite index.
4. (solved by @jbergman ) Let $H \leq G$ be a subgroup equipped with the subspace topology, $K\trianglelefteq G$ a normal subgroup, and $G/K$ equipped with the quotient space topology. Then $H$ and $G/K$ are again topological groups and the projection $\pi\, : \,G \twoheadrightarrow G/K$ is open.
5. $G$ is Hausdorff if and only if $\{1\}$ is a closed set in $G.$ $G/K$ is Hausdorff for a normal subgroup $K\trianglelefteq G,$ if and only if $K$ is closed in $G.$ If $G$ is totally disconnected, then $G$ is Hausdorff.
6. Let $G$ be a compact topological group and $\{X_j \;(j\in I)\}\subseteq G$ a family of closed subsets such that for all $i ,j\in I$ there is a $k\in I$ with $X_k\subseteq X_i\cap X_j.$ Then we have for any closed subset $Y\subseteq G$
   $$Y\cdot \left(\bigcap_{i\in I}X_i\right) = \bigcap_{i\in I} YX_i $$

6. Let $(X_n,d_n)_{n\in \mathbb{N}_0}$ be a sequence of complete metric spaces, and let $(f_n)_{n\in \mathbb{N}_0}$ be a sequence of continuous functions $f_n:X_{n+1}\longrightarrow X_n$ such that the image $f_n(X_{n+1}) \subseteq (X_n,d_n)$ is dense for all $n\in \mathbb{N}_0$. Then
$$
M_0:= \left\{v_0\in X_0\,|\,\exists\,(v_n)_{n\in \mathbb{N}} \,\forall\,n\in \mathbb{N}\, : \,v_n\in X_n\,\wedge \,f_{n-1}(v_n)=v_{n-1} \right\}
$$
and
$$
M_0\subseteq M:= \bigcap_{n=0}^\infty(f_0\circ f_1\circ\ldots\circ f_n)(X_{n+1})
$$
are dense in $(X_0,d_0).$ In particular $M\neq \emptyset$ in case $X_0\neq \emptyset.$


7. (solved by @julian ) Prove for all $x>-1$
$$
x-(1+x)\log (1+x)\leq -\dfrac{3x^2}{2(x+3)}
$$

8. (solved by @julian ) Let $(\Omega, \mathcal{A},\mathcal{P})$ be a probability space, $B,T,\sigma$ positive real numbers, and $n\in \mathbb{N}.$ For independently distributed random variables $X_1,\ldots,X_n\, : \,\Omega \longrightarrow \mathbb{R}$ with expectation values $E(X_k)=0$ and $E(X_k^2)\leq \sigma^2$, and boundary $\|X_k\|_\infty \leq B$ for all $k=1,\ldots,n$ prove
$$
P\left(\dfrac{1}{n}\sum_{k=1}^nX_k \geq \sqrt{\dfrac{2\sigma^2 T}{n}}+\dfrac{2BT}{3n}\right) \leq e^{-T}.
$$

9. Let $\mathbb{P}$ be the set of all primes, $p\in \mathbb{P},$ and $n\in \mathbb{N}$ a positive integer. $\operatorname{ord}_p(N)$ denotes the number of primes $p$ which occur as divisor in $\{1,2,\ldots,N\}$ counted by multiplicity. E.g. $N=24=4!$ and $p=3$ yields in $\{3=3^1,6=3^1\cdot 2,9=3^2,12=3^1\cdot 4,15=3^1\cdot 5,18=3^2\cdot 2,21=3^1\cdot 7,24=3^1\cdot 8\}$
$$
\operatorname{ord}_3(24) = 1+1+2+1+1+2+1+1=10
$$
Prove

1. (solved by @TeethWhitener ) $\displaystyle{\operatorname{ord}_p(n)=\sum_{k\geq 1}\left\lfloor \dfrac{n}{p^k}\right\rfloor}$
2. (solved by @TeethWhitener )$2\left.\,\right|\binom{2n}{n}$ and $p\left.\,\right|\binom{2n}{n}$ for all $n<p\leq 2n$
3. (solved by @TeethWhitener ) $p\geq 3\,\wedge \,2n/3 <p\leq n \,\Longrightarrow \,p\,\nmid\,\binom{2n}{n}$
4. (solved by @julian ) $p^r\left.\,\right|\binom{2n}{n}\,\Longrightarrow \,p^r\leq 2n$
5. (solved by @julian ) $\dfrac{2^{2n-1}}{n}\leq \binom{2n}{n}\leq 2^{2n-1}$
6. (solved by @julian ) $\displaystyle{\prod_{p\leq n}p<4^n}$

10. Let $K$ be compact and $C(K):=\{f:K\to \mathbb{R} \text{ or }\mathbb{C}\,|\,f \text{ is continuous}.$ A $n-$dimensional subspace $M\subseteq C(K)$ is called Haar space, if all $f\in M-\{0\}$ have at most $n-1$ zeros. Linear independent functions $S:=\{\varphi_1,\ldots,\varphi_n \}\subseteq C(K)$ are called a Chebyshev- or Haar-system, if $\operatorname{span}(S)$ is a Haar space. We denote the (compact) unit circle $\mathbb{T} := \{e^{2\pi it} \,|\, t\in [0,1)\}.$ Let $K\subseteq \mathbb{R}$ be compact or $K=\mathbb{T}\, , \,f\in C(K).$

We call a point $\xi \in K$ with $f(\xi)=0$ a simple zero of $f$ if $\xi$ is either on the boundary of $K$ or $f$ changes sign in $\xi.$ If $f(\xi -t)f(\xi +t)>0$ in a neighborhood of $\xi,$ then we speak of a double zero.

1. A subspace $M\subseteq C(K)$ with $\dim M=n$ is a Haar space if and only if each $f\in M-\{0\}$ that has $j\in \mathbb{N}_0$ simple zeros and $k\in \mathbb{N}_0$ double zeros holdsSo each element $f\in M-\{0\}$ has at most $n-1$ different zeros.
   $$j+2k<n. $$ So each element $f\in M-\{0\}$ has at most $n-1$ different zeros.
2. The space of all real-valued trigonometric polynomials on $[0,1)$ of degree at most $n$ is a Haar space of dimension $2n+1.$
3. Let $n\in \mathbb{N}_0,\;p\in T_n,$ and $x\in \mathbb{T}.$ Then
   $$
   \left|p'(x)\right|\leq 2\pi n\sqrt{\|p\|^2_\infty -|p(x)|^2}.
   $$
   Remark: Consider the linear differential operator $D(p)=p'$ on $T_n.$ From $|D(\sin(2\pi nx))|=|2\pi n\cos(2\pi nx)|$ we conclude that
   $$
   2\pi n \leq \|D\|=\sup_{\|p\|_\infty \leq 1}\|p'\|_\infty=\sup_{\|p\|_\infty = 1}\sup_{x\in \mathbb{T}}|p'(x)| <\infty
   $$
   because $T_n$ is finite-dimensional.

High Schoolers only (until 26th)
11. (solved by @Not anonymous ) Let $S$ be a set of real numbers that is closed under multiplication (that is, if $a$ and $b$ are in $S$, then so is $ab$). Let $T$ and $U$ be disjoint subsets of $S$ whose union is $S$. Given that the product of any three (not necessarily distinct) elements of $T$ is in $T$ and that the product of any three elements of $U$ is in $U$, show that at least one of the two subsets $T,U$ is closed under multiplication.12. (solved by @Not anonymous ) Suppose we have a necklace of $n$ beads. Each bead is labeled with an integer and the sum of all these labels is $n-1.$ Prove that we can cut the necklace to form a string whose consecutive labels $x_1, x_2,\ldots, x_n$ satisfy
$$
\sum_{i=1}^k x_i \leq k-1 \quad (k=1,\ldots,n).
$$

13. (solved by @Not anonymous ) Let $d:=d_1d_2\ldots d_9$ be a number with not necessarily distinct nine decimal digits. A number $e:=e_1e_2\ldots e_9$ is such that each of the nine digit numbers formed by replacing just one of the digits $d_j$ by the corresponding digit $e_j$ is divisible by $7$ for all $1\leq j\leq 9.$ A number $f:=f_1f_2\ldots f_9$ is formed the same way by starting with $e,$ i.e. each of the nine numbers formed by replacing a $e_k$ by $f_k$ is divisible by $7.$ Example: If $d=20210901$ then $e_6\in \{0,7\}$ since $7\,|\,20210001$ and $7\,|\,20210701 \,.$
Show that, for each $j,$ $d_j-f_j$ is divisible by $7.$14. An ellipse, whose semi-axes have lengths $a$ and $b$, rolls without slipping on the curve $y=c\sin(x/a).$ How are $a,b,c$ related, given that the ellipse completes one revolution when it traverses one period of the curve?15. (solved by @Not anonymous ) For a partition $\pi$ of $N:=\{1,2,\ldots\, , \,9\}$, let $\pi(x)$ be the number of elements in the part containing $x.$ Prove that for any two partitions $\pi_1$ and $\pi_2,$ there are two distinct numbers $x$ and $y$ in $N$ such that $\pi_j(x)=\pi_j(y)$ for $j=1,2.$

 

[PeroK]

I was confused by number 15, but I think I understand it now.

 

[martinbn]

Small nitpicking: I don't agree that a topological group and a Lie group are the same thing.

 

[fresh_42]

Small nitpicking: I don't agree that a topological group and a Lie group are the same thing.

Me neither. I said for example, and I hope you agree that a Lie group is indeed a topological group.

 

[martinbn]

Me neither. I said for example, and I hope you agree that a Lie group is indeed a topological group.

I see.

 

[Chestermiller]

In question 7, did you mean log or ln?

 

[benorin]

Spoiler: #1

#1) "Um, I'll take what is the Bohr-Mollerup Theorem for 200 points, Alex."

I want you honest opinions here, what do you think of my new signature? Simple yet amazing truth but is it too long?

 

[fresh_42]

In question 7, did you mean log or ln?

I meant $\ln$. I just think that $\log$ has become common if no basis is noted.

 

[fresh_42]

Spoiler: #1

#1) "Um, I'll take what is the Bohr-Mollerup Theorem for 200 points, Alex."

I want you honest opinions here, what do you think of my new signature? Simple yet amazing truth but is it too long?

I take Gauß for 500. (He defined it that way.)

 

[benorin]

I meant $\ln$. I just think that $\log$ has become common if no basis is noted.

In Computer Science $\log := \log _2$, in algebra 2 $\log := \log _{10}$, in Analysis $\log := \ln$.

 

[LCSphysicist]

I am really puzzled about the exercise 7. I think the use of calculus can simplify a lot the demonstration of the inequalitty, but i ask myself (and of course it is more elegante if it exist) if there is a way to show it without calculus (not derivatives basically)...

 

[fresh_42]

I am really puzzled about the exercise 7. I think the use of calculus can simplify a lot the demonstration of the inequalitty, but i ask myself (and of course it is more elegante if it exist) if there is a way to show it without calculus (not derivatives basically)...

I don't know. My solution uses derivatives. At least it is rather short.

 

[TeethWhitener]

Here's my completely non-rigorous first stab at problem 2:

Spoiler: Problem 2

Thought process: try to make the right side as small as possible and the left side as big as possible and show the inequality still holds.

(NB--I'm pretty sure we can assume WLOG that $x_1\leq x_2\leq\dots\leq x_m$, so that's what I'll be doing)

For any given sequence $T = (x_1,x_2,\dots,x_m)$, we have $\min(|T_1|)=m$. Such a situation occurs, e.g., for $T=(2,4,6,8,10)$. Here the only members of $T_1$ are the pairs where $i=j$; that is: $T_1=\{(x_1,x_1),(x_2,x_2),\dots,(x_m,x_m)\}$. For this case to hold, it must be true that $\forall i \neq j, |x_i-x_j|>1$. Using the assumption above that the sequence $T$ is ordered low to high, we'll let $|x_i-x_{i+1}|=1+\epsilon_{i}, \epsilon_{i}>0$. This means that, in this case, $\max(|x_i-x_j|)=(m-1)(1+\max(\epsilon_i))$, because there are $m-1$ gaps between the $m$ members of the sequence, and each gap is less than or equal to $1+\max(\epsilon_i)$.

We also have $\max(|T_r|)=m^2$. This arises in the case where all possible pairs are present in $T_r$. However, for the maximum case to hold, it must be the case that $r\geq\max(|x_i-x_j|)$. Keeping with the theme of my thought process from earlier, we want to make $r$ and $|T_1|$ as small as possible. So we have $r\geq (m-1)(1+\max(\epsilon_i))$ and we choose to make $\epsilon_i\ll 1$ to get $r$ as small as possible. Now, we know that $r$ is an integer, and that $r>m-1$, so that means $\min(r)=m$.

If we then plug into the inequality $\max(|T_r|)=m^2$, $\min(r)=m$, and $\min(|T_1|)=m$, we get
$$m^2<(2m-1)m$$
or
$$m>1$$
To finish up, when $m=1$, we have $|T_r|=|T_1|=1$ for all $r$, and the inequality holds trivially.

I'm not sure this constitutes a full proof, because I'm not sure if it properly excludes some intermediate values of $|T_1|$, $r$, and $|T_r|$ that could mess things up.

 

[fresh_42]

Here's my completely non-rigorous first stab at problem 2:

Spoiler: Problem 2

Thought process: try to make the right side as small as possible and the left side as big as possible and show the inequality still holds.

(NB--I'm pretty sure we can assume WLOG that $x_1\leq x_2\leq\dots\leq x_m$, so that's what I'll be doing)

For any given sequence $T = (x_1,x_2,\dots,x_m)$, we have $\min(|T_1|)=m$. Such a situation occurs, e.g., for $T=(2,4,6,8,10)$. Here the only members of $T_1$ are the pairs where $i=j$; that is: $T_1=\{(x_1,x_1),(x_2,x_2),\dots,(x_m,x_m)\}$. For this case to hold, it must be true that $\forall i \neq j, |x_i-x_j|>1$. Using the assumption above that the sequence $T$ is ordered low to high, we'll let $|x_i-x_{i+1}|=1+\epsilon_{i}, \epsilon_{i}>0$. This means that, in this case, $\max(|x_i-x_j|)=(m-1)(1+\max(\epsilon_i))$, because there are $m-1$ gaps between the $m$ members of the sequence, and each gap is less than or equal to $1+\max(\epsilon_i)$.

We also have $\max(|T_r|)=m^2$. This arises in the case where all possible pairs are present in $T_r$. However, for the maximum case to hold, it must be the case that $r\geq\max(|x_i-x_j|)$. Keeping with the theme of my thought process from earlier, we want to make $r$ and $|T_1|$ as small as possible. So we have $r\geq (m-1)(1+\max(\epsilon_i))$ and we choose to make $\epsilon_i\ll 1$ to get $r$ as small as possible. Now, we know that $r$ is an integer, and that $r>m-1$, so that means $\min(r)=m$.

If we then plug into the inequality $\max(|T_r|)=m^2$, $\min(r)=m$, and $\min(|T_1|)=m$, we get
$$m^2<(2m-1)m$$
or
$$m>1$$
To finish up, when $m=1$, we have $|T_r|=|T_1|=1$ for all $r$, and the inequality holds trivially.

I'm not sure this constitutes a full proof, because I'm not sure if it properly excludes some intermediate values of $|T_1|$, $r$, and $|T_r|$ that could mess things up.

Looks ok to me. My solution uses induction on $m$ and intervals $[x_i-1,x_i+1].$

 

[TeethWhitener]

For problem 9 part 1, I think you meant $\displaystyle{\operatorname{ord}_p(n!)=\sum_{k\geq 1}\left\lfloor \dfrac{n!}{p^k}\right\rfloor}$? If so, I think I have a bead on parts 1 and 2--maybe.

Spoiler: Problem 9 Part 1

$\displaystyle{\operatorname{ord}}_p(N)$ counts the number of times a prime appears in the divisor list of $\{1,2,\dots,N\}$ along with the multiplicity. But let's consider a different operator $\overline{\displaystyle{\operatorname{ord}}}_m(N)$ that is the same as $\displaystyle{\operatorname{ord}}_p(N)$ except it doesn't count multiplicity, and $m\in\mathbb{N}$ doesn't have to be prime. If we look, e.g., at $\overline{\displaystyle{\operatorname{ord}}}_2(n!)$, we add 1 every time we pass an even number in $\{1,2,\dots,n!\}$, which means $\overline{\displaystyle{\operatorname{ord}}}_2(n!)=\left\lfloor\frac{n!}{2}\right\rfloor$. Similarly, $\overline{\displaystyle{\operatorname{ord}}}_3(n!)=\left\lfloor\frac{n!}{3}\right\rfloor$, $\overline{\displaystyle{\operatorname{ord}}}_4(n!)=\left\lfloor\frac{n!}{4}\right\rfloor$, etc., and generally
$$\overline{\displaystyle{\operatorname{ord}}}_m(n!)=\left\lfloor\frac{n!}{m}\right\rfloor$$
To go from $\overline{\displaystyle{\operatorname{ord}}}_m(n!)$ to $\displaystyle{\operatorname{ord}}_p(n!)$, we note that
$$\displaystyle{\operatorname{ord}}_p(n!)=\sum_{k\geq1}{\overline{\displaystyle{\operatorname{ord}}}_{p^k}(n!)}=\sum_{k\geq 1}{\left\lfloor \dfrac{n!}{p^k}\right\rfloor}$$

Spoiler: Problem 9 Part 2

$p|\binom{2n}{n}$ is really easy. Since $p>n$, there is no $p$ in the denominator of $\binom{2n}{n}$. But since $p\leq 2n$, there is a $p$ in the numerator. So $p|\binom{2n}{n}$.

$2|\binom{2n}{n}$ is trickier. I think the point is to use the result from part 1, but I'm pretty sure it's easier via induction. Denoting $n!=2^xa$ and $(2n)!=2^yb$, where $2\nmid a$ and $2\nmid b$, we have that
$$\binom{2n}{n}=\frac{(2n)!}{n!n!}=\frac{2^yb}{2^{2x}a}$$
(This is where I start to lose rigor and question my approach.)
We can map each even number in the set $\{1,2,\dots,n\}$ to its double in the set $\{1,2,\dots,2n\}$. We can map each multiple of 4 in the original set to its double in the larger set, and do the same for each multiple of 8, etc., or $2^k$ generally. This mapping let's us write $y\geq (x+\left\lfloor\frac{n}{2}\right\rfloor)$. But this mapping isn’t surjective: we haven’t accounted for the factors of 2 in $(2n)!$ of the form $4j+2$. When we do that, we get that $y\geq (x+n)$.

To show that $\binom{2n}{n}$ is divisible by 2, we have to show that $y>2x$, or equivalently, $x<n$. Edit: the following is all incorrect. We do this by induction by proving: $n!<2^na, \forall a\in\mathbb{N}$.
Base step:
$1!=1<2a, \forall a\in\mathbb{N}$
Inductive step:
Let $n!<2^na, \forall a\in\mathbb{N}$. Then $(n+1)!=(n+1)n!<(n+1)2^na$. Since $(n+1)2^n<2^{n+1}$, we have $(n+1)!<2^{n+1}a$.

Edit: crap, ignore. Found an error in problem 9 part 2. May work on it later.

 

[fresh_42]

For problem 9 part 1, I think you meant $\displaystyle{\operatorname{ord}_p(n!)=\sum_{k\geq 1}\left\lfloor \dfrac{n!}{p^k}\right\rfloor}$? If so, I think I have a bead on parts 1 and 2--maybe.

Uhm, no. Consider my example: $10=8+2+0$. $24!$ has many, real many more divisors $3^k.$

Edit: crap, ignore. Found an error in problem 9 part 2. May work on it later.

 

[TeethWhitener]

Uhm, no. Consider my example: $10=8+2+0$. $24!$ has many, real many more divisors $3^k.$

$\displaystyle{\operatorname{ord}_3(4!)=\sum_{k\geq 1}\left\lfloor \dfrac{4}{3^k}\right\rfloor}=1$? I think it has to be factorial, or else I'm really missing something.

 

[fresh_42]

$\displaystyle{\operatorname{ord}_3(4!)=\sum_{k\geq 1}\left\lfloor \dfrac{4}{3^k}\right\rfloor}=1$? I think it has to be factorial, or else I'm really missing something.

Oops, you're right. I confused $4!=24$ with $24!$, sorry. I will correct the OP.

 

[TeethWhitener]

Thanks for the clarification. I still think my problem 9 part 1 is right. I think half of problem 9 part 2 is right too, but I'll have to work on the other half (I've struck through the wrong part in post 15).

 

[fresh_42]

Thanks for the clarification. I still think my problem 9 part 1 is right. I think half of problem 9 part 2 is right too, but I'll have to work on the other half (I've struck through the wrong part in post 15).

It would be nice if you wrote it again for $n$ instead of the faculty, and if possible with $n$ and $p$ fixed. It's actually quite easy, which is why I gathered so many parts.

 

[Not anonymous]

12. Suppose we have a necklace of beads. Each bead is labeled with an integer and the sum of all these labels is $n-1$. Prove that we can cut the necklace to form a string whose consecutive labels $x_1, x_2, \ldots, x_n$ satisfy $$
\sum_{i=1}^k x_i \leq k-1 \, \, (k=1,...,n).
$$

Does "cut the necklace to form a string" mean any rearrangement of the individual beads is allowed, or does it only mean making at most one cut anywhere in the necklace and swapping the 2 resulting parts to form a new sequence (meaning, for e.g., (1, 2, 3, 4, 5) →(3, 4, 5, 1, 2) is allowed but not (5, 2, 1, 4, 3))? If any reordering of beads is allowed, here is my attempted solution.

Spoiler: Question 12

Let $A = (a_1, a_2, ..., a_n)$ be the original sequence of integer-valued labels of the necklace's beads. We create a new sequence $X = (x_1, x_2, ..., x_n)$ using only values from $A$ (also, if some value is repeated in $A$, that value will be repeated the same number of times in the new sequence too, but the order may differ, i.e. cardinality of values is retained) but arranged in ascending (more precisely, non-decreasing) order, i.e. $x_i \leq x_{i+1} \, \forall i \in \{1,...,n-1\}$.

Define $S_k = \sum_{i=1}^k x_k, \, k=(1,...,n)$. Since $X$ contains the same values as $A$ and with same cardinality, the sums of all values in $X$ must be the same as that for $A$. Hence $S_n = \sum_{i=1}^k a_k = n-1$. ∴ $S_k$ meets the condition $S_k \leq k-1$ when $k=n$, and this becomes the initial case for induction.

Inductive step: We now show that if $S_k \leq k-1$ for $k=j$ where integer $j > 1$, then it must be true for $k=j-1$ too.

Proof by contradiction: Suppose $S_{j-1} > j-1$. Since $S_j = S_{j-1} + x_j$, $S_{j-1} > j-1$ implies that $x_j = S_j - S_{j-1} < (j-1) - (j-1) \Rightarrow x_j < 0$. (C1)

But if $S_{j-1} > (j-1)$ as assumed, it follows that $S_{j-1}$ is a positive integer (since $j > 1$) and therefore there must be at least one positive integer in $(x_1, ..., x_{j-1})$ since $S_{j-1}$ is the sum of these values by definition. (C2)

Conditions (C1) and (C2) cause a contradiction since $x_j < 0$ and $(x_1, ..., x_{j-1})$ containing a positive value imply that the values in $(x_1, ..., x_{j-1}, x_{j})$ do not follow a non-decreasing order as required by the definition of the sequence $X$. Since this contradiction eventually arises from the assumption that $S_{j-1} > j-1$, it must be the case that this assumption is incorrect and we must have $S_{j-1} \leq j-1$ instead. Hence the inductive step is proved, and by the method of induction, it follows that $$
S_k = \sum_{i=1}^k x_i \leq k-1 \, \, \forall k \in \{1,..., n\}
$$. Hence, the beads can be rearranged as required.

 

[fresh_42]

Does "cut the necklace to form a string" mean any rearrangement of the individual beads is allowed, or does it only mean making at most one cut anywhere in the necklace and swapping the 2 resulting parts to form a new sequence (meaning, for e.g., (1, 2, 3, 4, 5) →(3, 4, 5, 1, 2) is allowed but not (5, 2, 1, 4, 3))? If any reordering of beads is allowed, here is my attempted solution.

Cut means one cut, i.e. we make a string out of the circle and can so determine $x_n$. Order and given labels remain unchanged.

 

[TeethWhitener]

Here it is rewritten without the factorial. I wasn't quite sure what you meant by n and p fixed.

Spoiler: Problem 9 Part 1

$\displaystyle{\operatorname{ord}}_p(N)$ counts the number of times a prime appears in the divisor list of $\{1,2,\dots,N\}$ along with the multiplicity. But let's consider a different operator $\overline{\displaystyle{\operatorname{ord}}}_m(N)$ that is the same as $\displaystyle{\operatorname{ord}}_p(N)$ except it doesn't count multiplicity, and $m\in\mathbb{N}$ doesn't have to be prime. If we look, e.g., at $\overline{\displaystyle{\operatorname{ord}}}_2(n)$, we add 1 every time we pass an even number in $\{1,2,\dots,n\}$, which means $\overline{\displaystyle{\operatorname{ord}}}_2(n)=\left\lfloor\frac{n}{2}\right\rfloor$. Similarly, $\overline{\displaystyle{\operatorname{ord}}}_3(n)=\left\lfloor\frac{n}{3}\right\rfloor$, $\overline{\displaystyle{\operatorname{ord}}}_4(n)=\left\lfloor\frac{n}{4}\right\rfloor$, etc., and generally
$$\overline{\displaystyle{\operatorname{ord}}}_m(n)=\left\lfloor\frac{n}{m}\right\rfloor$$
To take into account multiplicity and go from $\overline{\displaystyle{\operatorname{ord}}}_m(n)$ to $\displaystyle{\operatorname{ord}}_p(n)$, we note that
$$\displaystyle{\operatorname{ord}}_p(n)=\sum_{k\geq1}{\overline{\displaystyle{\operatorname{ord}}}_{p^k}(n)}=\sum_{k\geq 1}{\left\lfloor \dfrac{n}{p^k}\right\rfloor}$$

I also found another error in 9-2, but I haven't figured out how to complete the problem yet. I'll think on it some more.

 

[fresh_42]

Here it is rewritten without the factorial. I wasn't quite sure what you meant by n and p fixed.

Spoiler: Problem 9 Part 1

$\displaystyle{\operatorname{ord}}_p(N)$ counts the number of times a prime appears in the divisor list of $\{1,2,\dots,N\}$ along with the multiplicity. But let's consider a different operator $\overline{\displaystyle{\operatorname{ord}}}_m(N)$ that is the same as $\displaystyle{\operatorname{ord}}_p(N)$ except it doesn't count multiplicity, and $m\in\mathbb{N}$ doesn't have to be prime. If we look, e.g., at $\overline{\displaystyle{\operatorname{ord}}}_2(n)$, we add 1 every time we pass an even number in $\{1,2,\dots,n\}$, which means $\overline{\displaystyle{\operatorname{ord}}}_2(n)=\left\lfloor\frac{n}{2}\right\rfloor$. Similarly, $\overline{\displaystyle{\operatorname{ord}}}_3(n)=\left\lfloor\frac{n}{3}\right\rfloor$, $\overline{\displaystyle{\operatorname{ord}}}_4(n)=\left\lfloor\frac{n}{4}\right\rfloor$, etc., and generally
$$\overline{\displaystyle{\operatorname{ord}}}_m(n)=\left\lfloor\frac{n}{m}\right\rfloor$$
To take into account multiplicity and go from $\overline{\displaystyle{\operatorname{ord}}}_m(n)$ to $\displaystyle{\operatorname{ord}}_p(n)$, we note that
$$\displaystyle{\operatorname{ord}}_p(n)=\sum_{k\geq1}{\overline{\displaystyle{\operatorname{ord}}}_{p^k}(n)}=\sum_{k\geq 1}{\left\lfloor \dfrac{n}{p^k}\right\rfloor}$$

I also found another error in 9-2, but I haven't figured out how to complete the problem yet. I'll think on it some more.

Yes, but you had not to define $\overline{ord}$. The same argument at the end works with $\left\lfloor \dfrac{n}{p}\right\rfloor\, , \,\left\lfloor \dfrac{n}{p^2}\right\rfloor\, , \,\left\lfloor \dfrac{n}{p^3}\right\rfloor,\ldots$ from the start.

 

[TeethWhitener]

It occurred to me as I was falling asleep that I was going about this problem in the most roundabout way possible.

Spoiler: Problem 9 part 2…again

To show that $2\,|\binom{2n}{n}$, we proceed via induction, which we should’ve just done from the beginning. We’re trying to establish that $$\frac{(2n)!}{n!n!}$$ is divisible by 2.
Base step ($n=1$):
$$\frac{2!}{1!1!}=2$$
Inductive step:
Let $\frac{(2n)!}{n!n!}$ be divisible by 2. Then consider $$\frac{(2n+2)!}{(n+1)!(n+1)!}=\frac{(2n+2)(2n+1)}{(n+1)(n+1)}\frac{(2n)!}{n!n!}$$ We have two cases:
1) $n+1$ is odd. In this case, the denominator doesn’t acquire any additional factors of 2, and we assumed that $\frac{(2n)!}{n!n!}$ was divisible by 2, so the whole expression is divisible by 2.
2) $n+1$ is even. In this case, the denominator acquires a factor of 4 which must be canceled in the numerator for the whole expression to remain divisible by 2. We see that if $n+1$ is even, then $n=2k+1$ for some integer $k$, and the numerator can be written as $(4k+2)!(4k+3)(4k+4)$. Thus we have explicitly a factor of 4 in the numerator to cancel the 4 in the denominator and the inductive step goes through.

 

[TeethWhitener]

Spoiler: Problem 9 part 3

Since $n\geq p>\frac{n}{2}$, each $n!$ in the denominator of $\binom{2n}{n}=\frac{(2n)!}{n!n!}$ will have one factor of $p$. Since $p>\frac{2n}{3}$, the numerator $(2n)!$ will have a factor of $p$ and a factor of $2p$ and no other factors of $p$. So the binomial coefficient will have the form $$\frac{p^2a}{p^2b}$$ The $p$’s will cancel out and the binomial coefficient will not be divisible by $p$.

 

[fresh_42]

It occurred to me as I was falling asleep that I was going about this problem in the most roundabout way possible.

Spoiler: Problem 9 part 2…again

To show that $2\,|\binom{2n}{n}$, we proceed via induction, which we should’ve just done from the beginning. We’re trying to establish that $$\frac{(2n)!}{n!n!}$$ is divisible by 2.
Base step ($n=1$):
$$\frac{2!}{1!1!}=2$$
Inductive step:
Let $\frac{(2n)!}{n!n!}$ be divisible by 2. Then consider $$\frac{(2n+2)!}{(n+1)!(n+1)!}=\frac{(2n+2)(2n+1)}{(n+1)(n+1)}\frac{(2n)!}{n!n!}$$ We have two cases:
1) $n+1$ is odd. In this case, the denominator doesn’t acquire any additional factors of 2, and we assumed that $\frac{(2n)!}{n!n!}$ was divisible by 2, so the whole expression is divisible by 2.
2) $n+1$ is even. In this case, the denominator acquires a factor of 4 which must be canceled in the numerator for the whole expression to remain divisible by 2. We see that if $n+1$ is even, then $n=2k+1$ for some integer $k$, and the numerator can be written as $(4k+2)!(4k+3)(4k+4)$. Thus we have explicitly a factor of 4 in the numerator to cancel the 4 in the denominator and the inductive step goes through.

Spoiler: Problem 9 part 3

Since $n\geq p>\frac{n}{2}$, each $n!$ in the denominator of $\binom{2n}{n}=\frac{(2n)!}{n!n!}$ will have one factor of $p$. Since $p>\frac{2n}{3}$, the numerator $(2n)!$ will have a factor of $p$ and a factor of $2p$ and no other factors of $p$. So the binomial coefficient will have the form $$\frac{p^2a}{p^2b}$$ The $p$’s will cancel out and the binomial coefficient will not be divisible by $p$.

Well, yes, I think. What do you think about my solution?

$\binom{2n}{n}=\binom{2n-1}{n-1}+\binom{2n-1}{n}=2\binom{2n-1}{n-1}\,\Longrightarrow \,2\,|\,\binom{2n}{n}$

$\binom{2n}{n}=\dfrac{2n\cdot\ldots\cdot(n+1)}{1\cdot\ldots\cdot n}$ and a prime $n<p\leq 2n$ in the numerator doesn't cancel.

 

[TeethWhitener]

What do you think about my solution?

I think I learned a new binomial coefficient identity

 

[Not anonymous]

Cut means one cut, i.e. we make a string out of the circle and can so determine $x_n$. Order and given labels remain unchanged.

Spoiler: Question 12

Let $A=(a_1, ..., a_n)$ denote the sequence of integer-valued labels of the necklace's beads, with some arbitrary bead chosen as the first one in the sequence and subsequent beads being selected in the order in which they appear in the necklace when moving in a clockwise direction. Define $S_k(A) = \sum_{i=1}^k a_i$. If $S_k(A) \leq k-1 \, \forall k \in \{0,...,n\}$ (call this condition C_sum), then cutting the necklace between $a_n$ and $a_1$ is the solution as it gives us the string $A$ which meets the desired criterion. But if $A$ does not meet the condition C_sum, we show that it is possible to rotate the sequence one or more times to get another sequence that meets the condition C_sum. In other words, we can start at any arbitrary bead on the necklace, look at the $n$ different sums $S_1(A), S_2(A),...,S_n(A)$ to check if it meets the condition C_sum, and if doesn't meet the condition, we should be able to rotate it a finite number of times to reach an ordered sequence that meets C_sum and therefore defines an appropriate position where to make the cut. We only need t consider necklaces having 2 or more beads since the proof is trivial for $n=1$.

Claim: If $A=(a_1, ..., a_n)$ is a sequence of values formed by starting from any arbitrary bead on the necklace as explained above and if $S_k(A) \leq k-1 \, \forall k \in \{K, K+1, ..., n\}$ for some integer $K > 1$ but there exists some $1 \leq j < K$ for which $S_{j}(A) > j-1$. Then it is possible to rotate it to form a sequence $B = (b_1, ..., b_n)$ such that $S_k(B) \leq k-1 \, \forall k \in \{K', K'+1, ..., n\}$ for some integer $1 \leq K' < K$, i.e. $B$ has more $k$ values in its "tail" than $A$ for which the $S_k(.) < k$ condition holds true.
Proof: We prove by the method of induction. Regardless of which bead is chosen as the first bead to form the sequence, the sum of $n$ labels will always be the same, $n-1$. Hence $S_k(A)$ is obviously true for $k=n$ and hence we may choose $K = n$ for the base case. (P0)

Let $j \geq 1$ be the smallest index such that $S_{k}(A) > k-1 \Rightarrow S_{j} \geq j$. And since it is the smallest such index, we must also have $S_{k} \leq k-1$ if $k < j$. (P1)
Consider the rotated sequence $B = (b_1, b_2, ..., b_n) = (a_{j+1}, a_{j+2}, ..., a_n, a_1, a_2, ..., a_j)$, i.e. formed by rotating the necklace by $j$ beads w.r.t. start of sequence $A$.

$S_{n-j}(B) = \sum_{i=1}^{n-j} b_i = (a_{j+1} + a_{j+2} + ... + a_{n}) = S_{n}(A) - S_{j}(A) \leq (n-1) - j \equiv (n-j)-1$ (P2)

For $k > n-j$, $S_{k}(B) = S_{n-j}(B) + (a_1 + ... + a_{k-(n-j)})$. By property (P1), if $k-(n-j) < j$, we have $\sum_{i=1}^{k-(n-j)} a_i \leq k-(n-j)-1 \Rightarrow S_k(B) \leq (n-j-1) + (k-(n-j)-1)$

$\Rightarrow S_k(b) \leq k-2 < k-1$, and if $k-(n-j) =j$, i.e. $k=n$ (the maximum possible value of $k$), then $S_k(B) = S_n(B) = n-1$. Hence $S_k(B) \leq k-1 \, \forall k \in \{n-j, n-j+1, ..., n\}$. Thus we have $K' = (n-j) < K$ such that $S_k(B) \leq k-1 \, \forall k \in \{K', K'+1, ..., n\}$, thus proving the claim.

Thus, as long as there exists some a "violating" offset $j \geq 1$, i.e. one for which $S_j(A) > j-1$ for some sequence $A$ of the necklace with an upper bound $K-1$ for $j$, we can rotate it to obtain another sequence $A$ such that if it at all it too has a "violating" offset $j'$, it will have a smaller upper bound $K'-1 < K-1$. Thus by rotating the necklace we can keep reducing the "violating" offset till we reach a sequence where no violating offset is present (it is reduced to 0), i.e. this new sequence meets the condition C_sum. Say this sequence is $X=(x_1, x_2, ..., x_n) = (a_{r+1}, ..., a_n, a_1, a_2, ..., a_r)$, i.e. obtained by rotating the starting sequence $A$ by $r$ beads. Then cutting the necklace between $a_r$ and $a_{r+1}$ gives us the desired sequence.

 

[fresh_42]

I have really difficulties reading this. The first paragraph is basically only repeating what has to be shown. It can be removed.

12.

Let $A=(a_1, ..., a_n)$ denote the sequence of integer-valued labels of the necklace's beads, with some arbitrary bead chosen as the first one in the sequence and subsequent beads being selected in the order in which they appear in the necklace when moving in a clockwise direction. Define $S_k(A) = \sum_{i=1}^k a_i$. If $S_k(A) \leq k-1 \, \forall k \in \{0,...,n\}$ (call this condition C_sum), then cutting the necklace between $a_n$ and $a_1$ is the solution as it gives us the string $A$ which meets the desired criterion. But if $A$ does not meet the condition C_sum, we show that it is possible to rotate the sequence one or more times to get another sequence that meets the condition C_sum. In other words, we can start at any arbitrary bead on the necklace, look at the $n$ different sums $S_1(A), S_2(A),...,S_n(A)$ to check if it meets the condition C_sum, and if doesn't meet the condition, we should be able to rotate it a finite number of times to reach an ordered sequence that meets C_sum and therefore defines an appropriate position where to make the cut. We only need t consider necklaces having 2 or more beads since the proof is trivial for $n=1$.

Claim: If $A=(a_1, ..., a_n)$ is a sequence of values formed by starting from any arbitrary bead on the necklace as explained above and if $S_k(A) \leq k-1 \, \forall k \in \{K, K+1, ..., n\}$ for some integer $K > 1$ but there exists some $1 \leq j < K$ for which $S_{j}(A) > j-1$. Then it is possible to rotate it to form a sequence $B = (b_1, ..., b_n)$ such that $S_k(B) \leq k-1 \, \forall k \in \{K', K'+1, ..., n\}$ for some integer $1 \leq K' < K$, i.e. $B$ has more $k$ values in its "tail" than $A$ for which the $S_k(.) < k$ condition holds true.

And here I am getting lost. What is $K$ meant to be? As I see it, we can simply say $K=n$ and $j$ is a counterexample. It is neither the maximal nor the minimal index that violates the condition. You always say "some". That makes it difficult to handle sequences. You have a sequence $1,\ldots, K-1$ with "some" $K$ and "some" $j <K$. You do not say what the induction variable is. I assume $K$ since you say $K=n$ is your base case. Do you perform the induction backwards, or do you work with a minimal counterexample? But then you mentioned earlier $n=1$ as trivial case. What are you trying to do? I only see "some" and countless unspecified indices.

Here is a hint:
Consider $S_k= x_1 +\ldots+x_k - \dfrac{k(n-1)}{n}$ with $k=0,1,\ldots,n$ and $S_0=0.$

Proof: We prove by the method of induction. Regardless of which bead is chosen as the first bead to form the sequence, the sum of $n$ labels will always be the same, $n-1$. Hence $S_k(A)$ is obviously true for $k=n$ and hence we may choose $K = n$ for the base case. (P0)

Let $j \geq 1$ be the smallest index such that $S_{k}(A) > k-1 \Rightarrow S_{j} \geq j$. And since it is the smallest such index, we must also have $S_{k} \leq k-1$ if $k < j$. (P1)
Consider the rotated sequence $B = (b_1, b_2, ..., b_n) = (a_{j+1}, a_{j+2}, ..., a_n, a_1, a_2, ..., a_j)$, i.e. formed by rotating the necklace by $j$ beads w.r.t. start of sequence $A$.

$S_{n-j}(B) = \sum_{i=1}^{n-j} b_i = (a_{j+1} + a_{j+2} + ... + a_{n}) = S_{n}(A) - S_{j}(A) \leq (n-1) - j \equiv (n-j)-1$ (P2)

For $k > n-j$, $S_{k}(B) = S_{n-j}(B) + (a_1 + ... + a_{k-(n-j)})$. By property (P1), if $k-(n-j) < j$, we have $\sum_{i=1}^{k-(n-j)} a_i \leq k-(n-j)-1 \Rightarrow S_k(B) \leq (n-j-1) + (k-(n-j)-1)$

$\Rightarrow S_k(b) \leq k-2 < k-1$, and if $k-(n-j) =j$, i.e. $k=n$ (the maximum possible value of $k$), then $S_k(B) = S_n(B) = n-1$. Hence $S_k(B) \leq k-1 \, \forall k \in \{n-j, n-j+1, ..., n\}$. Thus we have $K' = (n-j) < K$ such that $S_k(B) \leq k-1 \, \forall k \in \{K', K'+1, ..., n\}$, thus proving the claim.

Thus, as long as there exists some a "violating" offset $j \geq 1$, i.e. one for which $S_j(A) > j-1$ for some sequence $A$ of the necklace with an upper bound $K-1$ for $j$, we can rotate it to obtain another sequence $A$ such that if it at all it too has a "violating" offset $j'$, it will have a smaller upper bound $K'-1 < K-1$. Thus by rotating the necklace we can keep reducing the "violating" offset till we reach a sequence where no violating offset is present (it is reduced to 0), i.e. this new sequence meets the condition C_sum. Say this sequence is $X=(x_1, x_2, ..., x_n) = (a_{r+1}, ..., a_n, a_1, a_2, ..., a_r)$, i.e. obtained by rotating the starting sequence $A$ by $r$ beads. Then cutting the necklace between $a_r$ and $a_{r+1}$ gives us the desired sequence.

 

[julian]

An idea of a proof of the Bohr-Mollerup theorem:

Spoiler

Let

\begin{align*}
\Gamma_n (x) = \frac{n! n^x}{x (x+1) \cdots (x + n)}
\end{align*}

\begin{align*}
\log \Gamma_n (x) = \log (n!) + x \log n - \sum_{m=0}^n \log (x + m)
\end{align*}

We have

\begin{align*}
\frac{d^2}{dx^2} \log \Gamma_n (x) = \sum_{m=0}^n \frac{1}{(x + m)^2} \geq 0 .
\end{align*}

meaning that it is a convex function. As the limit of a sequence of convex functions is convex we have that the log of $\Gamma (x)$ is convex. $\Gamma (0) = 1$. Also,

\begin{align*}
\Gamma (x + 1) = \lim_{n \rightarrow \infty} \frac{n! n^x n}{(x + 1) (x+2) \cdots (x + n + 1)} = \lim_{n \rightarrow \infty} \frac{n! n^x}{x (x+1) \cdots (x + n)} \cdot x \frac{n}{x + n + 1} = x \cdot \Gamma (x)
\end{align*}

So $\Gamma (x)$ satisfies the required conditions specified in the problem.

Note that

\begin{align*}
\lim_{x \rightarrow \infty} \frac{d^2}{dx^2} \log \Gamma (x) = 0 .
\end{align*}

To attempt to prove uniqueness consider

\begin{align*}
d (x) = \log G(x) - \log \Gamma (x)
\end{align*}

or

\begin{align*}
e^{d (x)} = G (x) / \Gamma (x)
\end{align*}

where $G (x)$ has the same properties as listed in the problem, which we just proved for $\Gamma (x)$.

We easily have that $d(0) = 0$. Also $d (x+1) = d (x)$ and so $d (x)$ is periodic.

Write

\begin{align*}
\frac{d^2}{dx^2} d (x) = \frac{d^2}{dx^2} \log G(x) - \frac{d^2}{dx^2} \log \Gamma (x) .
\end{align*}

Suppose that $d (x)$ is not constant. If we can then show that there exists an $x_0$ such that

\begin{align*}
\frac{d^2}{dx^2} d (x_0) < 0 ,
\end{align*}

then, using the periodicity of $d (x)$ we would have

\begin{align*}
\frac{d^2}{dx^2} d (x_0) & = \lim_{n \rightarrow \infty} \frac{d^2}{dx^2} d (x_0 + n)
\nonumber \\
& = \lim_{n \rightarrow \infty} \frac{d^2}{dx^2} \log G (x_0 + n) - \lim_{n \rightarrow \infty} \frac{d^2}{dx^2} \log \Gamma (x_0 + n)
\nonumber \\
& = \lim_{n \rightarrow \infty} \frac{d^2}{dx^2} \log G(x + n) \geq 0
\end{align*}

producing a contradiction. We would then have that $d (x)$ is constant. Since $d(0) = 0$, $d (x) =0$ for all $x$. Implying $G (x) = \Gamma (x)$.

Say we always had that

\begin{align*}
\frac{d^2}{dx^2} d (x) \geq 0 ,
\end{align*}

then this would rule out periodic functions that are convex in places and concave in other places. But there are most likely going to be counter examples to these functions. I think I can think of some already.

I am very tired now. Tomorrow.

[SPLOILER]

 

[MathematicalPhysicist]

Spoiler: Problem 1

$$f(x)=f(x+1)/x=f(x+2)/(x(x+1))=\ldots = f(x+n)/(x(x+1)\ldots (x+n))$$

Spoiler: #1

#1) "Um, I'll take what is the Bohr-Mollerup Theorem for 200 points, Alex."

I want you honest opinions here, what do you think of my new signature? Simple yet amazing truth but is it too long?

Spoiler

I've seen a proof of this theorem in Askey's Special Functions red book.
And I am perplexed, why can you assume that $n$ is a positive integer and $0<x<1$?
It's on page: 35.

 

[julian]

I was hoping @fresh_42 would point out what periodic functions I'm not considering and maybe give a suggestion as to complete the proof I have started.

 

[fresh_42]

Spoiler: Problem 1

$$f(x)=f(x+1)/x=f(x+2)/(x(x+1))=\ldots = f(x+n)/(x(x+1)\ldots (x+n))$$

Spoiler

I've seen a proof of this theorem in Askey's Special Functions red book.
And I am perplexed, why can you assume that $n$ is a positive integer and $0<x<1$?
It's on page: 35.

$n>0$ can be assumed since we consider a limit with $n \to \infty$.
You first show $f(x+n)=(x+n-1)(x-n-2)\cdots (x+1)xf(x).$
Note that $f$ is defined by properties. And these properties are all we are allowed to use. Using too many $\Gamma 's$ makes the proof unreadable!

Next, we have to show with the help of this formula, that for any $y=x+N\in (N,N+1]$ holds $f(y)=\Gamma(y)$ where a) remember that $\Gamma(y)$ is defined as a limit here (see problem statement, and not as the gamma function) and which is b) the first essential part of the proof.

Then we can take log's and show (remember that $\Gamma$ is a limit): $L_n\leq f(x) \leq R_n$ with $L_n,R_n\to \Gamma(x)$.

This is at least the proof structure of my solution. I am skeptical if $\Gamma 's$ are used to make it misty because everybody has the faculty in mind.

The theorem says:
Gauß's definition of the gamma function as a limit is a necessary consequence of the functional requirements.

It's necessity which is the crucial point, not that it suffices.

 

[fresh_42]

I was hoping @fresh_42 would point out what periodic functions I'm not considering and maybe give a suggestion as to complete the proof I have started.

Well, I tried to provide hints in my previous post. I would be happy if you used less $G's$ and $\Gamma 's$ in your prove. This only creates confusion.

 

[julian]

Well, I tried to provide hints in my previous post. I would be happy if you used less $G's$ and $\Gamma 's$ in your prove. This only creates confusion.

The only reason I considered $\Gamma_n (x)$'s was to prove for finite $n$ that these functions are convex, which would then imply that the limit function $\lim_{n \rightarrow \infty} \Gamma_n (x)$ is convex. I was proving that the limit function stated in the problem satisfies the properties stated in the problem.

I then wanted to prove that it is is the only function that satisfies the properties (uniqueness proof part) and so I necessarily had to introduce an arbitrary function $G (x)$ that also satisfies the properties stated in the problem.

(I made a few edits to my partial solution to make it a bit clearer and correct some typos)

 

[julian]

I think that a U-shaped function over a unit interval, repeated would produce a continuous periodic function satisfying $\frac{d^2 d (x)}{dx^2} \geq 0$ as so would spoil the uniqueness part of my proof. I will later attempt to modify my proof to incorporate such functions.

 

[fresh_42]

Would you mind answering the following remarks?

An idea of a proof of the Bohr-Mollerup theorem:

Let

\begin{align*}
\Gamma_n (x) = \frac{n! n^x}{x (x+1) \cdots (x + n)}
\end{align*}

\begin{align*}
\log \Gamma_n (x) = \log (n!) + x \log n - \sum_{m=0}^n \log (x + m)
\end{align*}

We have

\begin{align*}
\frac{d^2}{dx^2} \log \Gamma_n (x) = \sum_{m=0}^n \frac{1}{(x + m)^2} \geq 0 .
\end{align*}

Note to self: there is no restriction on the domain. $x$ is arbitrary here.

meaning that it is a convex function. As the limit of a sequence of convex functions is convex we have that the log of $\Gamma (x)$ is convex. $\Gamma (0) = 1$.

This is why I dislike the use of $\Gamma(x)$ here. We need $\Gamma(1)=1$ to be a solution.

Also,

\begin{align*}
\Gamma (x + 1) = \lim_{n \rightarrow \infty} \frac{n! n^x n}{(x + 1) (x+2) \cdots (x + n + 1)} = \lim_{n \rightarrow \infty} \frac{n! n^x}{x (x+1) \cdots (x + n)} \cdot x \frac{n}{x + n + 1} = x \cdot \Gamma (x)
\end{align*}

So $\Gamma (x)$ satisfies the required conditions specified in the problem.

Note that

\begin{align*}
\lim_{x \rightarrow \infty} \frac{d^2}{dx^2} \log \Gamma (x) = 0 .
\end{align*}

To attempt to prove uniqueness consider

\begin{align*}
d (x) = \log G(x) - \log \Gamma (x)
\end{align*}

Come on! $d$ as a function name where you use differentials, too? Really?

My problem, however, is another one. You have shown (or tried to) that the limit fulfills the functional equations. How can you (logically) use this limit again (hidden in $\Gamma(x)$) to prove uniqueness? All you are allowed to use are the functional equations, not the form of a single solution.

$\Gamma(x)$ shouldn't occur anymore from here on.

Or do you want to show that any other solution is arbitrarily close to the given one? In which metric? Pointwise? It would help a lot if you would explain what you want to do.

or

\begin{align*}
e^{d (x)} = G (x) / \Gamma (x)
\end{align*}

where $G (x)$ has the same properties as listed in the problem, which we just proved for $\Gamma (x)$.

We easily have that $d(0) = 0$. Also $d (x+1) = d (x)$ and so $d (x)$ is periodic.

Write

\begin{align*}
\frac{d^2}{dx^2} d (x) = \frac{d^2}{dx^2} \log G(x) - \frac{d^2}{dx^2} \log \Gamma (x) .
\end{align*}

Suppose that $d (x)$ is not constant. If we can then show that there exists an $x_0$ such that

\begin{align*}
\frac{d^2}{dx^2} d (x_0) < 0 ,
\end{align*}

then, using the periodicity of $d (x)$ we would have

\begin{align*}
\frac{d^2}{dx^2} d (x_0) & = \lim_{n \rightarrow \infty} \frac{d^2}{dx^2} d (x_0 + n)
\nonumber \\
& = \lim_{n \rightarrow \infty} \frac{d^2}{dx^2} \log G (x_0 + n) - \lim_{n \rightarrow \infty} \frac{d^2}{dx^2} \log \Gamma (x_0 + n)
\nonumber \\
& = \lim_{n \rightarrow \infty} \frac{d^2}{dx^2} \log G(x + n) \geq 0
\end{align*}

producing a contradiction. We would then have that $d (x)$ is constant. Since $d(0) = 0$, $d (x) =0$ for all $x$. Implying $G (x) = \Gamma (x)$.

Say we always had that

\begin{align*}
\frac{d^2}{dx^2} d (x) \geq 0 ,
\end{align*}

then this would rule out periodic functions that are convex in places and concave in other places. But there are most likely going to be counter examples to these functions. I think I can think of some already.

The idea is correct. Maybe you should consider the following: Assume $d(x)$ is not constant, then there are $x,y>0$ with e.g. $g(y)>g(x).$ By periodicty we may assume $x<y<x+1.$ Now consider the second divided difference
$$
-\dfrac{\log f(x)}{x-y}+\dfrac{\log f(y)}{(y-x)(y-x-1)}-\dfrac{\log f(x+1)}{x-y+1}
$$

 

[MathematicalPhysicist]

$n>0$ can be assumed since we consider a limit with $n \to \infty$.
You first show $f(x+n)=(x+n-1)(x-n-2)\cdots (x+1)xf(x).$
Note that $f$ is defined by properties. And these properties are all we are allowed to use. Using too many $\Gamma 's$ makes the proof unreadable!

Next, we have to show with the help of this formula, that for any $y=x+N\in (N,N+1]$ holds $f(y)=\Gamma(y)$ where a) remember that $\Gamma(y)$ is defined as a limit here (see problem statement, and not as the gamma function) and which is b) the first essential part of the proof.

Then we can take log's and show (remember that $\Gamma$ is a limit): $L_n\leq f(x) \leq R_n$ with $L_n,R_n\to \Gamma(x)$.

This is at least the proof structure of my solution. I am skeptical if $\Gamma 's$ are used to make it misty because everybody has the faculty in mind.

The theorem says:
Gauß's definition of the gamma function as a limit is a necessary consequence of the functional requirements.

It's necessity which is the crucial point, not that it suffices.

And why can we assume that $x<1$?
@fresh_42 I am referring to the proof in Askey's red book on special functions.

I can copy the proof from the book, but should I bother?

 

[fresh_42]

And why can we assume that $x<1$?

You have to show it. I laid out a way to do so.

@fresh_42 I am referring to the proof in Askey's red book on special functions.

I can copy the proof from the book, but should I bother?

Wait for Julian's solution.

 

[Not anonymous]

And here I am getting lost. What is $K$ meant to be? As I see it, we can simply say $K=n$ and $j$ is a counterexample. It is neither the maximal nor the minimal index that violates the condition. You always say "some".

Just as I feared, my answer caused more confusion than clarification with its use of indices. I tried to keep the use of different indices to the minimum but couldn't avoid using $i, j, K, K', n$ with the way I tried to explain. Admittedly, my proof is too verbose and not the most elegant. I had in fact tried to get a more formulaic proof such as by transforming all labels by subtracting the average (similar to your hint, though without $k$ multiplying the average), but didn't think deep enough along that line to get to a proof; and I am not a quick problem solver. The proof I gave is more procedural and came more naturally when I tried to solve, Also, I shouldn't have called it proof by induction, though my method shares some similarities with an inductive proof. Let me try explain my proof in less mathematical terms, through a sequence of logical statements. If there is some error or gap in these statements, please do let me know so that I can learn and correct, and will attempt to solve using the hint you have provided later.

1. For any sequence $A=(a_1, ..., a_n)$, we define $S_k(A) = \sum_{i=1}^k a_i (k=1,...,n)$. We say an index $j$ is a "violating index" if $S_j(A) > j-1$.
2. If the sequence does not have a violating index, then we have already got a sequence that defines the cut in a straightforward way - cut the necklace between $a_n$ and $a_1$ to get the desired string.
3. If $A$ corresponds to labels of the $n$ consecutive beads starting from an arbitrarily chosen bead in the necklace, all we can say is that if it has one or more violating indices, those indices are upper-bounded by $n-1$, since $S_n(A) = n-1$ and so $n$ can never be a violating index. We may denote by $K$ this upper bound, and in this start case, $K=n-1$ (minor difference from earlier posted solution - there I used $K=n$ to denote 1 + upper bound)
4. Now, if $A$ has 1 or more violating indices upper bounded by $K$, we take the smallest violating index $j$ and based on that define a rotated sequence $B = (a_{j+1}, a_{j+2, ..., a_n, a_1, ..., a_j})$. As proved in my earlier post, this rotated sequence cannot have any violating index that falls in the "tail" subsequence $(a_1, ..., a_j)$ (that subsequence that moved from being at the start of $A$ to the end of $B$) or even $a_n$. Any violating index, if present, should lie in the head subsequence $(a_{j+1}, ..., a_{n-1})$, i.e. in that part of the earlier sequence $A$ that has now been shifted left. Hence, the upper bound on violating indices has also shifted left when we formed $B$, so the upper bound index $K'$ (corresponding to $B$) must be smaller than $K$ of $A$.
5. The above observations imply that we will always able to rotate any sequence with a violating index to form another sequence whose violating indices will have a smaller upper bound. Thus, we can start from any randomly chosen bead in the necklace and by performing a finite number of rotations (at most $n-1$, to be more specific), we can reach a sequence that has no violating offset. This sequence gives the desired string and the cut to be performed on the necklace is chosen accordingly.

 

[fresh_42]

Just as I feared, my answer caused more confusion than clarification with its use of indices. I tried to keep the use of different indices to the minimum but couldn't avoid using $i, j, K, K', n$ with the way I tried to explain.

This is ok as long as you rigorously define them. "Some" is insufficient.

Admittedly, my proof is too verbose and not the most elegant. I had in fact tried to get a more formulaic proof such as by transforming all labels by subtracting the average (similar to your hint, though without $k$ multiplying the average), but didn't think deep enough along that line to get to a proof;

The idea with the sum $S(k)$ I mentioned is basically similar to what you did, only without bothering the many possible locations $i,j,K,K',n.$

Observe that $S(0)=S(n)=0$. Then some index has to be the maximum (or minimum, depending on the signs in $S(k).$) The maximum now defines the split, and all you have to do is, to show, that this choice of $x_n$ works.

Very similar to your argument.

and I am not a quick problem solver. The proof I gave is more procedural and came more naturally when I tried to solve, Also, I shouldn't have called it proof by induction, though my method shares some similarities with an inductive proof. Let me try explain my proof in less mathematical terms, through a sequence of logical statements. If there is some error or gap in these statements, please do let me know so that I can learn and correct, and will attempt to solve using the hint you have provided later.

1. For any sequence $A=(a_1, ..., a_n)$, we define $S_k(A) = \sum_{i=1}^k a_i (k=1,...,n)$. We say an index $j$ is a "violating index" if $S_j(A) > j-1$.
2. If the sequence does not have a violating index, then we have already got a sequence that defines the cut in a straightforward way - cut the necklace between $a_n$ and $a_1$ to get the desired string.
3. If $A$ corresponds to labels of the $n$ consecutive beads starting from an arbitrarily chosen bead in the necklace, all we can say is that if it has one or more violating indices, those indices are upper-bounded by $n-1$, since $S_n(A) = n-1$ and so $n$ can never be a violating index. We may denote by $K$ this upper bound, and in this start case, $K=n-1$ (minor difference from earlier posted solution - there I used $K=n$ to denote 1 + upper bound)
4. Now, if $A$ has 1 or more violating indices upper bounded by $K$, we take the smallest violating index $j$ and based on that define a rotated sequence $B = (a_{j+1}, a_{j+2, ..., a_n, a_1, ..., a_j})$. As proved in my earlier post, this rotated sequence cannot have any violating index that corresponds to the "tail" subsequence $(a_1, ..., a_j)$ (that subsequence that moved from being at the start of $A$ to the end of $B$). Any violating index, if present, should lie in the head subsequence $(a_{j+1}, ..., a_n)$, i.e. in that part of the earlier sequence $A$ that has now been shifted left. Hence, the upper bound on violating indices has also shifted left when we formed $B$, so the upper bound index $K'$ (corresponding to $B$) must be smaller than $K$ of $A$.
5. The above observations imply that we will always able to rotate any sequence with a violating index to form another sequence whose violating indices will have a smaller upper bound. Thus, we can start from any randomly chosen bead in the necklace and by performing a finite number of rotations (at most $n-1$, to be more specific), we can reach a sequence that has no violating offset. This sequence gives the desired string and the cut to be performed on the necklace is chosen accordingly.

 

[julian]

I'm extremely tired right now so go easy on me. Let me clarify the method of proof I'm attempting:

----

First I establish that the limit function:

\begin{align*}
\lim_{n \rightarrow \infty} \frac{n! n^x}{x (x+1) \cdots (x + n)}
\end{align*}

satisfies all the conditions stated in the question:

Let $f$ be a function defined on $(0, \infty)$ such that for all $f (x) > 0$ for all $x > 0$

\begin{align*}
\log f (x) \text{ is convex} , \quad f (x+1) = x \cdot f (x) , \quad f(1) = 1 .
\end{align*}

Next I prove that the limit function (which I denote by $\Gamma (x)$) is the only function that satisfies the above conditions. I do this the standard way. I introduce an arbitrary function that satisfies the above conditions and then I form the difference between the logs:

\begin{align*}
d (x) = \log G (x) - \log \Gamma (x)
\end{align*}

and then prove that $d (x) = 0$ for all $x > 0$ (which here is done by first proving that $d (x)$ is a constant). A lot of the time you do this by proof by contradiction. I'm allowed to use properties of the function $\Gamma (x)$ in doing this, if fact you must somehow use properties of $\Gamma (x)$ in doing this.

----

I've used the functional conditions to obtain properties of $d (x)$ and I'm attempting to use these together with asymptotic behaviour of $d^2 \Gamma (x) / dx^2$ (and the assumption that $G (x)$ is convex) to obtain a contradiction thereby proving $d (x)$ to be constant.

(Note: most of the time you consider the difference between the functions rather than the difference between their logs, it doesn't matter here).

 

[julian]

Hi @fresh_42. Here are my comments in relation to post #38.

(a)

I said:

“We have

\begin{align*}
\frac{d^2}{dx^2} \log \Gamma_n (x) = \sum_{m=0}^n \frac{1}{(x + m)^2} \geq 0 .
\end{align*}”

This is because in the question you say the function is defined on $(0 , \infty)$. Are you saying I should have mentioned this in my proof?

(b)

$\Gamma (0) =1$ is a typo.

(c)

$d (x)$ doesn't stand for differential. I choose $d$ to denote the function because I was considering the difference between two functions.

I think I have shown the limit function satisfies the functional conditions. I forgot to mention that the limit function is $> 0$ for $x \in (0 , \infty)$.

(d)

@fresh_42 said:

“Or do you want to show that any other solution is arbitrarily close to the given one? In which metric? Pointwise? It would help a lot if you would explain what you want to do. ”

That is kind of the idea. I'm doing the standard thing of introducing an arbitrary function, $G (x)$, that satisfies the above functional conditions and then forming the difference between the log of $G (x)$ and the log of $\Gamma (x)$:

\begin{align*}
d(x) = log⁡G(x) − log ⁡\Gamma (x)
\end{align*}

and then attempting to prove that $d(x)=0$ for all $x>0$ (which here is done by first proving that $d(x)$ is a constant).Given that the limit function ($=: \Gamma (x)$) is the only function that satisfies the functional conditions, how can you talk about other solutions converging to it? (It has been proven other ways that it is the only function satisfying the functional conditions).

So I'm not attempting to prove that other solutions converge to the limit function ($=: \Gamma (x)$). I'm attempting to outright prove that the limit function is the only solution to the functional conditions. I'm (attempting) to do this by proving that if any alternative solution exists you would get a contradiction.

(e)

I know about polynomial interpolations, including Newton's polynomial and how to establish that its coefficients are the $n-$th divided difference via algebra and proof by induction. I know that in the limit that where point become nodes converge you get $\frac{1}{n!} d^n f (x) / dx^n$ for the $n-$th coefficient. I'm really tired right now. I'll have to think about it later.LAST remark: you are a a lot of the time you are just saying that my explanation could be clearer?

 

[fresh_42]

Hi @fresh_42. Here are my comments in relation to post #38.

(a)

I said:

“We have

\begin{align*}
\frac{d^2}{dx^2} \log \Gamma_n (x) = \sum_{m=0}^n \frac{1}{(x + m)^2} \geq 0 .
\end{align*}”

This is because in the question you say the function is defined on $(0 , \infty)$. Are you saying I should have mentioned this in my proof?

Forget it. I just saw the first differential and wondered where $\log n$ has gone to. It's late here, too.

(b)

$\Gamma (0) =1$ is a typo.

(c)

$d (x)$ doesn't stand for differential. I choose $d$ to denote the function because I was considering the difference between two functions.

I think I have shown the limit function satisfies the functional conditions. I forgot to mention that the limit function is $> 0$ for $x \in (0 , \infty)$.

Yes, you did. Modulo the typo and my disability to do two differentiations in mind.

(d)

@fresh_42 said:

“Or do you want to show that any other solution is arbitrarily close to the given one? In which metric? Pointwise? It would help a lot if you would explain what you want to do. ”

That is kind of the idea. I'm doing the standard thing of introducing an arbitrary function, $G (x)$, that satisfies the above functional conditions and then forming the difference between the log of $G (x)$ and the log of $\Gamma (x)$:

\begin{align*}
d(x) = log⁡G(x) − log ⁡\Gamma (x)
\end{align*}

and then attempting to prove that $d(x)=0$ for all $x>0$ (which here is done by first proving that $d(x)$ is a constant).

Sure. But it is an unlucky choice. You could have used $\Delta$ or $\operatorname{dist}.$

Given that the limit function ($=: \Gamma (x)$) is the only function that satisfies the functional conditions, how can you talk about other solutions converging to it? (It has been proven other ways that it is the only function satisfying the functional conditions).

So I'm not proving that other solutions converge to the limit function ($=: \Gamma (x)$). I'm attempting to outright prove that the limit function is the only solution that satisfies the functional conditions. I'm (attempting) to do this by proving that if any alternative solution exists you would get a contradiction.

(e)

I know about polynomial interpolations, including Newton's polynomial and how to establish that its coefficients are the $n-$th divided difference via algebra and proof by induction. I know that in the limit that where point become nodes converge you get $\frac{1}{n!} d^2 f (x) / dx^2$ for the $n-$th coefficient. I'm really tired right now. I'll have to think about it later.LAST remark: you are a a lot of the time that my explanation could be clearer?

Yes, sorry. That is why your proofs cannot be read without a lot of brainwork or with paper and pencil in hand. And I have had one of the less bright days today.

Reading a proof (which wasn't my version) requires a lot of care in order to get possible loopholes. And if it isn't written for dummies, then it is sometimes quite exhausting. You probably have seen a few textbooks in your life, yet. Did you ever notice that some authors have a writing style that suits you better than others?

Last remark: How do you know that $G(x)$ is twice differentiable? Newton's interpolations avoid that problem.

 

[julian]

I don't know if Randall R. Holmes has written any books but he has written notes. I've gone through a lot of notes and algebra and Galois theory. It is all laid out clearly, not overly wordy, and it's like he often he knows where you brain is going to go next and steps in.

 

[jbergman]

I don't understand what 1 is asking? Are you looking for a proof that f(x) is what you said it was?

 

[fresh_42]

I don't understand what 1 is asking? Are you looking for a proof that f(x) is what you said it was?

Yes. Given a function with properties 1,2,3, prove that it is this limit.

 

[jbergman]

5. A group $G$ together with a topology, such that the mapping on $G\times G$ (equipped with the product topology) to $G$ given by $(x,y)\longmapsto xy^{-1}$ is continuous, is called a topological group (e.g. a Lie group). Prove

1. $G$ is a topological group if and only if inversion and multiplication are continuous.
2. The mappings $x\longmapsto xg$ and $x\longmapsto gx$ are homeomorphisms for each $g\in G.$
3. Each open subgroup $U\leq G$ is closed, and each closed subgroup $U\leq G$ of finite index is open. If $G$ is compact, then each open subgroup is of finite index.
4. Let $H \leq G$ be a subgroup equipped with the subspace topology, $K\trianglelefteq G$ a normal subgroup, and $G/K$ equipped with the quotient space topology. Then $H$ and $G/K$ are again topological groups and the projection $\pi\, : \,G \twoheadrightarrow G/K$ is open.
5. $G$ is Hausdorff if and only if $\{1\}$ is a closed set in $G.$ $G/K$ is Hausdorff for a normal subgroup $K\trianglelefteq G,$ if and only if $K$ is closed in $G.$ If $G$ is totally disconnected, then $G$ is Hausdorff.
6. Let $G$ be a compact topological group and $\{X_j \;(j\in I)\}\subseteq G$ a family of closed subsets such that for all $i ,j\in I$ there is a $k\in I$ with $X_k\subseteq X_i\cap X_j.$ Then we have for any closed subset $Y\subseteq G$
   $$Y\cdot \left(\bigcap_{i\in I}X_i\right) = \bigcap_{i\in I} YX_i $$

1. If $G$ is a topological group then, $inv(g) = (e,g) \longmapsto eg^{-1} = g^{-1}$ is continuous. Also, $(g, inv(h)) \longmapsto gh$ is continuous, since it is the composition of continuous maps. The other direction is trivial because $gh^{-1}$ is again the composition of continuous maps and hence gives the required continuous map for a topological group.

2. The kernel of both maps is empty since group operations are invertible. We can exhibit an inverses $x \longmapsto xg^{-1}$ and $x \longmapsto g^{-1}x$ respectively.

 

[julian]

Just want to make a comment, before moving on to proving that the limit function is the unique solution of the functional conditions.

I wanted to prove that the limit function:

\begin{align*}
\lim_{n \rightarrow \infty} \frac{n! n^x}{x (x+1) \cdots (x + n)} =: \Gamma (x)
\end{align*}

satisfies all the conditions stated in the question. In particular I wanted to prove that the limit function is log-convex. So I began by proving the sequence of functions:

\begin{align*}
\Gamma_n (x) = \frac{n! n^x}{x (x+1) \cdots (x + n)}
\end{align*}

are log-convex. You then can then apply Theorem 1.6 of Artin's notes:

http://inis.jinr.ru/sl/vol1/UH/_Ready/Mathematics/Advanced calculus/Artin E. The Gamma function (1931)(L)(23s).pdf

which states that "A convergent sequence of log-convex functions has a log-convex limit function, provided the limit is positive". These conditions are satisfied and so the limit function is log-convex. Verifying the other functional conditions was straightforward.

I now want to prove that the limit function ($\Gamma (x)$) is the only function that satisfies the functional conditions, but first I need to give some definitions and theorems

Some definitions and theorems:

Given data points $(x_0 , f (x_0)) , (x_1 , f (x_1)) , (x_2, f (x_2))$, the first divided difference is defined by

\begin{align*}
f [x_0,x_1] = \frac{f (x_1) - f (x_0)}{x_1 - x_0} = f [x_1,x_0]
\end{align*}

The second divided difference is defined by

\begin{align*}
f [x_0,x_1,x_2] & = \frac{f [x_1,x_2] - f [x_0,x_1]}{x_2 - x_0}
\nonumber \\
& = \frac{\frac{f (x_2) - f (x_1)}{x_2 - x_1} - \frac{f (x_1) - f (x_0)}{x_1 - x_0}} {x_2 - x_0}
\nonumber \\
& = \frac{f (x_0)}{(x_1 - x_0) (x_2 - x_0)} - \frac{f (x_1)}{(x_2 - x_1) (x_1 - x_0)} + \frac{f (x_2)}{(x_2 - x_1) (x_2 - x_0)} \quad (*)
\nonumber \\
& = \frac{(x_2 - x_1) f (x_0) + (x_0 - x_2) f (x_1) + (x_1 - x_0) f (x_2)}{(x_0 - x_1) (x_1 - x_2) (x_2 - x_0)}
\end{align*}

The last line demonstrates that the second divided difference is invariant under permutation of the arguments $x_0 , x_1 , x_2$.

If we permute $x_0$ and $x_1$ and use $f [x_1 , x_0] = f [x_0 , x_1]$ then we have;

\begin{align*}
f [x_0,x_1,x_2] & = \frac{f [x_0 , x_2] - f [x_0 , x_1]}{x_2 - x_1}
\end{align*}

The function $f (x)$ is convex (on the interval $(a,b)$) if for every number $x_0$ of the interval, $f [x_0 , x_2]$ is a monotonically increasing function of $x_2$. This means that for any pair of numbers $x_2 > x_1$ distinct from $x_0$ the inequality $f [x_0 , x_2] \geq f [x_0 , x_1]$ holds; in other words $f [x_0,x_1,x_2] \geq 0$. Since the value of $f [x_0,x_1,x_2]$ is not changed by permutation of the arguments, the convexity of $f$ is equivalent to the inequality

\begin{align*}
f [x_0,x_1,x_2] \geq 0
\end{align*}

for all triples of distinct numbers on the interval (as explained in Artin's notes, though I'm using slightly different notation). This demonstrates that the "second divided difference" does encode whether a function is convex or not.

We will need the mean value theorem for divided differences:

https://en.wikipedia.org/wiki/Mean_value_theorem_(divided_differences)

For the case $n = 2$ it states that For any $3$ pairwise distinct points $x_0 , x_1 , x_2$ in the domain of a twice differentiable function $f$ there exists an interior point $\xi$

\begin{align*}
\xi \in (\min \{ x_0 , x_1 , x_2 \} , \max \{ x_0 , x_1 , x_2 \})
\end{align*}

where the $2$nd derivative of $f$ equals $2!$ times the $2$nd divided difference at this point:

\begin{align*}
f [x_0,x_1,x_3] = \frac{f'' (\xi)}{2!}
\end{align*}

Proof of uniqueness:

I now prove that the limit function ($\Gamma (x)$) is the only function that satisfies the functional conditions. I do this the standard way. I introduce an arbitrary function, $G (x)$, that satisfies the functional conditions and then I form the difference between the logs:

\begin{align*}
r (x) = \log G (x) - \log \Gamma (x)
\end{align*}

and then prove that $r (x) = 0$ for all $x > 0$. We do this by considering the second divided difference of the above function:

\begin{align*}
r [x_0 , x_1 , x_2] = \log G [x_0 , x_1 , x_2] - \log \Gamma [x_0 , x_1 , x_2]
\end{align*}

and by using the functional conditions, the properties of $\Gamma (x)$, and the mean value theorem for divided differences.

It was proven in a previous post, using the functional conditions, that $r$ is periodic: $r (x+1) = r (x)$ and that $r (1) = 0$. Suppose that $r$ is not constant, then there are $x,y > 0$ with $r(y) > r(x)$. By periodicity we may assume $x < y < x + 1$. Let $x_0 = x$, $x_1 = y$, and $x_2 = x + 1$ in equation $(*)$ where we are taking $f$ to be the function $r$. Then using the periodicity of $r$ we establish the inequality

\begin{align*}
r [x , y , x + 1] & = \frac{r(x)}{y - x} - \frac{r (y)}{(x + 1 - y) (y - x)} + \frac{r (x + 1)}{x + 1 - y}
\nonumber \\
& = \frac{r (x) - r (y)}{(y - x) (x + 1 - y)} < 0
\end{align*}

As $\Gamma (x)$ is log-convex on $(0, \infty)$ we have

\begin{align*}
\log \Gamma [x_0 , x_1, x_2] \geq 0 .
\end{align*}

for all triples of distinct numbers. Same statement applies to the function $G (x)$.

By the periodicity of $r$ we have that

\begin{align*}
r [x , y , x + 1] & = r [x + n , y + n , x + n + 1]
\nonumber \\
& = \log G [x + n , y + n , x + n + 1] - \log \Gamma [x + n , y + n , x + n + 1] .
\end{align*}

Rearranged we have

\begin{align*}
r [x , y , x + 1] + \log \Gamma [x + n , y + n , x + n + 1] = \log G [x + n , y + n , x + n + 1] \qquad (**)
\end{align*}

By the mean value theorem for divided differences, we have that:

\begin{align*}
\log \Gamma [x + n , y + n , x + n + 1] & = \frac{1}{2} \frac{d^2}{dx^2} \log \Gamma (\xi) \qquad \text{for some } \xi \in (x + n , x + n + 1)
\nonumber \\
& \leq \frac{1}{2} \max_{z \in (x + n , x + n + 1)} \frac{d^2}{dx^2} \Gamma (z)
\end{align*}

In a previous post we demonstrated that $\lim_{x \rightarrow \infty} \frac{d^2}{dx^2} \Gamma (x) \rightarrow 0$. By choosing $n$ large enough the LHS of $(**)$ becomes negative and we have a contradiction since $\log G [x + n , y + n , x + n + 1]$ is supposed to be non-negative. Therefore, $r (x)$ must be a constant. Given that $r (1) = 0$ this means that $r (x) = 0$ for all $x \in (0 , \infty)$ and so $\Gamma (x)$ is indeed the unique solution to the functional conditions.