Let $c_n$ be a sequence which is defined recursively as follows: $c_0 = 1$, $c_{2n+1} = c_n$ for $n \geq 0$, and $c_{2n} = c_n + c_{n-2^e}$ for $n > 0$ where $e$ is the maximal nonnegative integer such that $2^e$ divides $n$. Prove that \[\sum_{i=0}^{2^n-1} c_i = \frac{1}{n+2} {2n+2 \choose n+1}.\]
Problem
Source: USA TST 2011 P5
Tags: induction, modular arithmetic, function, limit, algebra, polynomial, binomial theorem
darij grinberg
28.07.2011 22:55
According to property (m) of the Catalan numbers in Richard Stanley's Exercises on Catalan and Related Numbers, the $n+1$-th Catalan number $C_{n+1}$ equals the number of unordered pairs of lattice paths with $n$ steps each, starting at $\left(0,0\right)$, using steps $\left(0,1\right)$ and $\left(1,0\right)$, ending at the same point, such that one path never arises above the other path. If we define an $\ell_n$-path to mean a lattice path with $n$ steps, starting at $\left(0,0\right)$, using steps $\left(0,1\right)$ and $\left(1,0\right)$, then this rewrites as follows: $C_{n+1}$ equals the number of unordered pairs of $\ell_n$-paths ending at the same point, such that one path never arises above the other path. Let us reformulate this with ordered pairs (instead of unordered ones): $C_{n+1}$ equals the number of ordered pairs $\left(p,q\right)$ of $\ell_n$-paths ending at the same point, such that the path $q$ never rises above the path $p$. In other words, (1) $C_{n+1} = \sum\limits_{p\text{ is an }\ell_n\text{-path}} \left(\text{number of }\ell_n\text{-paths ending at the same point as }p\text{ and never arising above }p\right)$. Now, we notice that we can encode an $\ell_n$-path as a binary string of length $n$, namely by scanning it from right to left and coding every $\left(0,1\right)$ step as $0$ and every $\left(1,0\right)$ step as $1$. This binary string, then, can be seen as the binary representation of some $i\in\left\{0,1,...,2^n-1\right\}$. Thus we have got a bijection between $\ell_n$-paths and elements of $\left\{0,1,...,2^n-1\right\}$. If $i$ denotes the element of $\left\{0,1,...,2^n-1\right\}$ corresponding to a given $\ell_n$-path $p$, then it turns out that $c_i$ is the number of $\ell_n$-paths ending at the same point as $p$ and never arising above $p$. This is proven by induction over $i$ (more precisely, by the kind of induction where you assume something holds for $i$ and conclude that it holds for $2i$ and $2i+1$ as well). I won't go into details for now. Anyway, this solves the problem, as it transforms (1) into the claim of the problem. I am wondering whether this is the proposed solution, and how property (m) of the Catalan numbers is proven. (Then again, I could probably look this up in Stanley...)
MellowMelon
29.07.2011 00:25
Your solution resembles the proposed one as far as it being a bijection. I don't think anyone who solved the problem gave a solution that wasn't one, but pretty much everyone's was different. Yours too; I never saw one using that method of counting the Catalan numbers. Here's what I thought was a very clean method: We use the bijection from number of $n$ balanced pairs of parentheses to $C_n$. Write $i$ in binary as $\overline{d_1 d_2 \ldots d_n}$, adding leading zeroes if necessary. We claim that $c_i$ counts the number of balanced pairs of $n+1$ parentheses such that for $k = 1, \ldots n$, the $2k$th parenthesis is open if $d_k = 1$ and closed otherwise. For $c_0$, we are given that the parenthesis in positions $2, 4, \ldots 2n$ are all closed, and position $2n+2$ also has a closed parenthesis. Thus all $n+1$ closed parentheses are specified, and filling the remaining spaces with open parentheses gives a valid expression. So $c_0 = 1$. Next, we wish to show $c_{2n+1} = c_n$. Consider an arbitrary expression counted by $c_{2n+1}$. The $2n$th, or 3rd to last, parenthesis is open, and the only way for this to be balanced is to end in $\ldots())$. Take the $()$ in positions $2n, 2n+1$ and move it to the beginning of the expression. This places a $)$ in the second position and shifts all other parentheses except the last over by 2, and this corresponds exactly to a valid expression for $c_n$. The inverse operation is easy to write down, so this is a bijection. Now consider $c_{2n}$ for $n > 0$. Consider the last 1 in the binary expansion of $2n$, corresponding to the last $($ in an even-numbered position. By assumption the parenthesis two to its right is closed, so we have $\ldots(?)\ldots$. a) If the $?$ is $($, take it with the $)$ to its right and move them to the beginning. This gets us a valid expression for $c_n$, and is also invertible. b) If the $?$ is $)$, take it with the $($ to its left and move them to the beginning. This gets us a valid expression for $c_{n-2^e}$ where $2^e$ is the maximal power of 2 dividing $n$ because we took the last 1 in the binary expansion. It is also invertible given $e$. So $c_{2n} = c_n + c_{n-2^e}$. The work above proves our claim about what the $c_i$ count. If we sum $c_i$ from $0$ to $2^n - 1$, we get all possible expressions of $n+1$ balanced pairs of parentheses, equal to $C_{n+1}$, which completes the proof. EDIT re below: Yes, you're right, I flipped things around in the base case. It's been fixed now. Thanks.
darij grinberg
29.07.2011 22:28
MellowMelon wrote: For $c_0$, we are given that the parenthesis in positions $2, 4, \ldots 2n$ are all open, and position 1 also has an open parenthesis. Thus all $n+1$ open parentheses are specified, and filling the remaining spaces with closed parentheses gives a valid expression. So $c_0 = 1$. Shouldn't this rather be: For $c_0$, we are given that the parenthesis in positions $2, 4, \ldots 2n$ are all closed, and position $2n+2$ also must have a closed parenthesis. Thus all $n+1$ closed parentheses are specified, and filling the remaining spaces with open parentheses gives a valid expression. So $c_0 = 1$. Nice proof - so I now do know how to prove property (m) of the Catalan numbers
Zhero
29.07.2011 22:39
For $n \geq 0$ and $m \geq 0$, let
\[ s_{n,m} = \displaystyle \sum_{\substack{0 \leq i < 2^n \\ i \equiv 2^m \pmod{2^{m+1}}}} c_i, \]
let
\[ t_{n,m} = \displaystyle \sum_{\substack{0 \leq i < 2^n \\ i \equiv 0 \pmod{2^m}}} c_i, \]
and let
\[ u_n = \sum_{m \geq 0}^{\infty} s_{n,m} = \sum_{i=0}^{2^n - 1} c_i. \]
We observe that $s_{0,0} = 1$, $s_{0,m} = 0$ for $m > 0$, that
\[ s_{n,0} = \sum_{\substack{0 \leq i < 2^n \\ i \equiv 1 \pmod{2}}} c_i = \sum_{0 \leq i < 2^{n-1}} c_{2i+1} = \sum_{0 \leq i < 2^{n-1}} c_i = u_{n-1}, \]
and that
\[ t_{n,0} = \sum_{\substack{0 \leq i < 2^n \\ i \equiv 0 \pmod{1}}} c_i = \sum_{0 \leq i < 2^n} c_i = u_n. \]
Also, for $m,n \geq 1$, we have
\begin{align*}
s_{n,m}
&= \sum_{\substack{0 \leq i < 2^n \\ i \equiv 2^m \pmod{2^{m+1}}}} c_i = \sum_{\substack{0 \leq i < 2^{n-1} \\ i \equiv 2^{m-1} \pmod{2^m}}} c_{2i} = \sum_{\substack{0 \leq i < 2^{n-1} \\ i \equiv 2^{m-1} \pmod{2^m}}} (c_i + c_{i - 2^{m-1}}) \\
&= \sum_{\substack{0 \leq i < 2^{n-1} \\ i \equiv 2^{m-1} \pmod{2^m}}} c_i + \sum_{\stackrel{0 \leq i < 2^{n-1}}{i \equiv 0 \pmod{2^m}}} c_i = s_{n-1,m-1} + t_{n-1,m} \tag{1}
\end{align*}
and that for $m, n \geq 0$,
\[ t_{n,m} = \sum_{\substack{0 \leq i < 2^n \\ i \equiv 0 \pmod{2^m}}} c_i = \sum_{\substack{0 \leq i < 2^n \\ i \equiv 2^m \pmod{2^{m+1}}}} c_i + \sum_{\stackrel{0 \leq i < 2^n}{i \equiv 0 \pmod{2^{m+1}}}} c_i = s_{n,m} + t_{n,m+1}. \]
Combining this with (1), we get that for $m, n \geq 1$, we have $t_{n-1,m-1} = s_{n-1,m-1} + t_{n-1,m} = s_{n,m}.$ Thus, for $n \geq 1$, we have $s_{n,1} = t_{n-1,0} = u_{n-1}$, and for $n \geq 1$ and $m \geq 1$, we have $s_{n,m} = s_{n-1,m-1} + t_{n-1,m} = s_{n-1,m-1} + s_{n,m+1},$ whence $s_{n+1, m+2} = s_{n+1, m+1} - s_{n,m}$ whenever $m, n \geq 0$.
In summary, we have arrived at the following recurrence: $s_{0,m} = 1$ for all $m$, $s_{n,0} = s_{n,1} = \sum_{m=0}^{\infty} s_{n-1,m} = u_{n-1}$ for all $n \geq 1$, and $s_{n+1,m+2} = s_{n+1,m+1} - s_{n,m}$ for all $m,n \geq 0$, and we wish to show that $u_n = C_{n+1}$ for all $n \geq 0$.
Let $B_n(x) = \sum_{m=0}^{\infty} s_{n,m} x^m$ be the generating function for $\{s_{n,k}\}_{k=0}^{\infty}$. From the above recurrence, we have $B_0(x) = 1$, $[x^0]B_n(x) = [x^1]B_n(x) = u_{n-1} = B_{n-1}(1)$ for all $n \geq 1$, and
\[ \frac{B_{n+1}(x) - u_n x - u_n}{x^2} = \frac{B_{n+1}(x) - u_n}{x} - B_n(x), \]
which rearranges to
\[ B_{n+1}(x) = \frac{x^2 B_n(x) - u_n}{x-1}. \]
We compute a few terms:
\[ B_0(x) = 1, \\ B_1(x) = \frac{x^2}{x-1} - \frac{u_0}{x-1}, \\ B_2(x) = \frac{x^4}{(x-1)^2} - \frac{u_1}{x-1} - \frac{u_0 x^2}{(x-1)^2} , \\ B_3(x) = \frac{x^6}{(x-1)^3} - \frac{u_2}{x-1} - \frac{u_1 x^2}{(x-1)^2} - \frac{u_0 x^4}{(x-1)^3}, \]
from which it is clear (and can easily be shown by induction) that
\[ B_n(x) = \frac{x^{2n}}{(x-1)^n} - \sum_{k=0}^{n-1} \frac{u_{n-1-k} x^{2k}}{(x-1)^{k+1}} = \frac{x^{2n} - \sum_{k=0}^{n-1} u_{n-1-k} (x-1)^{n-k-1} x^{2k}}{(x-1)^n}. \]
We will now show by induction that $u_n = C_{n+1}$. Our base case, $n=0$, is obvious. Suppose that for some $n > 1$, we have $u_i = C_{i+1}$ for all $0 \leq i < n$. Then we wish to show that $u_n = B_n(1) = C_{n+1}$. Observe that
\[ B_n(1) = \lim_{x \to 1} B_n(x) = \lim_{x \to 1}\frac{x^{2n} - \sum_{k=0}^{n-1} u_{n-1-k} (x-1)^{n-k-1} x^{2k}}{(x-1)^n}. \]
Because this limit must exist and $(x-1)^n$ has multiplicity $n$, we may apply l'Hopital's rule $n$ times to get
\[ \lim_{x \to 1}\frac{x^{2n} - \sum_{k=0}^{n-1} u_{n-1-k} (x-1)^{n-k-1} x^{2k}}{(x-1)^n} = \lim_{x \to 1} \frac{\frac{d^n}{dx^n} \left( x^{2n} - \sum_{k=0}^{n-1} u_{n-1-k} (x-1)^{n-k-1} x^{2k} \right) }{ \frac{d^n}{dx^n} (x-1)^n }. \]
Subtituting $u_i = C_{i+1}$, we have
\begin{align*}
B_n(1)
&= \lim_{x \to 1} \frac{\frac{d^n}{dx^n} \left( x^{2n} - \sum_{k=0}^{n-1} C_{n-k} (x-1)^{n-k-1} x^{2k} \right) }{ \frac{d^n}{dx^n} \left( (x-1)^n \right) } \\
&= \lim_{x \to 1} \frac{ n! \binom{2n}{n} - \sum_{k=0}^{n-1} C_{n-k} \frac{d^n}{dx^n} \left( (x-1)^{n-k-1} x^{2k} \right)}{n!} \\
&= \binom{2n}{n} - \frac{1}{n!} \sum_{k=0}^{n-1} C_{n-k} \left( \frac{d^n}{dx^n} \left( (x-1)^{n-k-1} x^{2k} \right) \Bigg |_{x=1}\right) .
\end{align*}
According to the General Leibniz rule, we have
\[ \frac{d^n}{dx^n} \left( (x-1)^{n-k-1} x^{2k} \right) \Bigg |_{x=1} = \sum_{i=0}^n \binom{n}{i} \left( \frac{d^i}{dx^i} (x-1)^{n-k-1} \Bigg |_{x=1} \right) \left( \frac{d^{n-i}}{dx^{n-i}} x^{2k} \Bigg |_{x=1} \right). \]
Note that $\frac{d^i}{dx^i} (x-1)^{n-k-1} \Bigg |_{x=1}$ equals 0 if $i \neq n-k-1$, and equals $(n-k-1)!$ if $i=n-k-1$. Thus, each summand in the above sum is 0 except when $i=n-k-1$, so
\[ \frac{d^n}{dx^n} \left( (x-1)^{n-k-1} x^{2k} \right) \Bigg |_{x=1} = \binom{n}{n-k-1} (n-k-1)! \frac{(2k)!}{(k-1)!} = n! \binom{2k}{k+1}. \]
Observing that $\binom{2k}{k+1} = k C_k$ and substituting, we have
\[ B_n(1) = \binom{2n}{n} - \sum_{k=0}^{n-1} k C_{n-k} C_k. \]
Let
\[ S = \sum_{k=0}^n k C_{n-k} C_k = \sum_{k=0}^n (n-k) C_{n-(n-k)} C_{n-k} = \sum_{k=0}^n (n-k) C_{n-k} C_k. \]
We have
\[ S = \frac{\sum_{k=0}^n (k + n-k) C_{n-k} C_k}{2} = \frac{n}{2} \sum_{k=0}^n C_{n-k} C_k = \frac{n C_{n+1}}{2}. \]
Thus,
\begin{align*}
B_n(1) &= \binom{2n}{n} - \sum_{k=0}^{n-1} k C_{n-k} C_k = (n+1) C_n - (S - n C_n) = (n+1) C_n + n C_n - \frac{n}{2} C_{n+1} = (2n+1) C_n - \frac{n}{2} C_{n+1} \\
&= \frac{n+2}{2} C_{n+1} - \frac{n}{2} C_{n+1} = C_{n+1},
\end{align*}
that is, $u_n = B_n(1) = C_{n+1}$, as desired.
Quote: I don't think anyone who solved the problem gave a solution that wasn't one, but pretty much everyone's was different. So I guess my progress was not really counted as a solution. (I did everything the same until I said "use the general Leibniz rule"; instead, I said "we can use the binomial theorem and the recurrence for Catalan numbers to finish"... oops?)
Sung-yoon Kim
14.08.2011 13:21
This problem was proposed by me. My first solution uses a bijection counting some kinds of lattice paths, and second solution calculates the sum algebraically.
math154
15.09.2011 02:44
Zhero wrote:
For $n \geq 0$ and $m \geq 0$, let
\[ s_{n,m} = \displaystyle \sum_{\substack{0 \leq i < 2^n \\ i \equiv 2^m \pmod{2^{m+1}}}} c_i, \]
let
\[ t_{n,m} = \displaystyle \sum_{\substack{0 \leq i < 2^n \\ i \equiv 0 \pmod{2^m}}} c_i, \]
and let
\[ u_n = \sum_{m \geq 0}^{\infty} s_{n,m} = \sum_{i=0}^{2^n - 1} c_i. \]
There's a (small, I guess, depending on your intuition?) issue with this: $v_2(0)=\infty$, so $c_0$ is only included in $s_{n,\infty}$. For example, we actually have $s_{0,0}=0$, not $s_{0,0}=1$. But the method is sound, and a little tweaking works...
Let
\[s_{n,m}=\sum_{0\le i<2^n,\; v_2(i)=m} c_i.\] for $n,m\ge0$. Then $s_{0,m}=0$ for all $m\ge0$ and $s_{n,m}=0$ if $m\ge n\ge0$. Because
\[\sum_{i=0}^{2^n-1}c_i = \sum_{i=1}^{2^n-1}c_{2i+1} = s_{n+1,0},\]it suffices to show that $s_{n,0}=C_n$ for all $n\ge1$, i.e. $G_n(0)=C_n$ for all $n\ge1$, where $G_n(x)=\sum_{m\ge0} s_{n,m}x^m$.
It's easy to see using $c_{2k+1}=c_k$ and $c_{2k}=c_k+c_{k-2^{v_2(k)}}$ that for $n\ge1$,
\[s_{n,0} = 1 + \sum_{j\ge0} s_{n-1,j},\]and for $n>m\ge1$,
\[s_{n,m} = 1 + \sum_{j\ge m-1} s_{n-1,j}.\]Clearly $G_0(x)=0$, so for $n\ge1$,
\begin{align*}
G_n(x) = \sum_{m\ge0} s_{n,m}x^m = \sum_{m=0}^{n-1} s_{n,m}x^m
&= 1 + \sum_{j\ge0} s_{n-1,j} + \sum_{m=1}^{n-1}\left(1 + \sum_{j\ge m-1} s_{n-1,j}\right) \\
&= \frac{x^n-1}{x-1} + \sum_{j=0}^{n-2} s_{n-1,j}\frac{x^{j+2}-1}{x-1} \\
&= \frac{x^n-1+x^2G_{n-1}(x)-G_{n-1}(1)}{x-1}.
\end{align*}Thus $G_n(0)=1+G_{n-1}(1)$ for all $n\ge1$ (*).
Now we'll induct on $n\ge1$ to show that $G_n(0)=C_n$, where the base case $G_1(0)=C_1=1$ is obvious. If $n\ge2$, then by a simple induction with our recursion for $G_n(x)$ and the inductive hypothesis,
\[G_n(x) = \sum_{k=1}^{n} \frac{x^{2n-k} - C_k x^{2n-2k}}{(x-1)^{n+1-k}} = \sum_{k=1}^{n} \frac{x^{2n-k}(x-1)^{k-1} - C_k x^{2n-2k}(x-1)^{k-1}}{(x-1)^n}.\]By the general Leibniz rule,
\[[(x^a(x-1)^b)^{(n)}]_{x=1} = \binom{n}{b}[(x^a)^{(n-b)}]_{x=1}b! = n!\binom{a}{n-b},\]so using (*) and l'Hôpital's rule $n$ times "in reverse order" (note that $G_n(x)$ is a polynomial, so $1$ is a root of multiplicity at least $n$ in $(x-1)^nG_n(x)$),
\begin{align*}
G_{n+1}(0) = 1+G_n(1) = 1+\lim_{x\to1} G_n(1)
&= 1+\lim_{x\to1} \frac{\sum_{k=1}^{n} x^{2n-k}(x-1)^{k-1} - C_k x^{2n-2k}(x-1)^{k-1}}{(x-1)^n} \\
&= 1+\lim_{x\to1} \frac{\sum_{k=1}^{n} n!\binom{2n-k}{n-k+1} - C_k n!\binom{2n-2k}{n-k+1}}{n!} \\
&= 1+\sum_{k=1}^{n} \binom{2n-k}{n-k+1} - \sum_{k=1}^{n} C_k \binom{2n-2k}{n-k+1} \\
&= \sum_{k=n-1}^{2n-1} \binom{k}{n-1} - \sum_{k=1}^{n} C_k \left(\binom{2(n-k)}{n-k} - C_{n-k}\right) \\
&= \binom{2n}{n} + C_{n+1}-C_0C_n + C_0\binom{2n}{n} - \sum_{k=0}^{n}\frac{1}{k+1}\binom{2k}{k}\binom{2(n-k)}{n-k} \\
&= C_{n+1} + 2\binom{2n}{n} - C_n - \frac{1}{2}\sum_{k=0}^{n}\frac{(k+1)+(n-k+1)}{(k+1)(n-k+1)}\binom{2k}{k}\binom{2(n-k)}{n-k} \\
&= C_{n+1} + \frac{2n+1}{n+1}\binom{2n}{n} - \frac{n+2}{2}\sum_{k=0}^{n}C_kC_{n-k} \\
&= C_{n+1} + \binom{2n+1}{n+1} - \frac{n+2}{2}C_{n+1} \\
&= C_{n+1} + \binom{2n+1}{n} - \frac{1}{2}\binom{2n+2}{n+1} \\
&= C_{n+1},
\end{align*}as desired.
ChanandlerBong
16.07.2023 16:09
The number $\frac{1}{n+2}{2n+2 \choose n+1}$ is the $n+1$-th Catalan number, which is equal to the cardinality of $$X:=\{(x_0,x_1,\dots, x_{n+1})\in \mathbb{Z}^{n+2}\mid 0=x_0\leq x_1\leq \dots \leq x_{n+1}=n+1, \quad x_i\leq i \quad \text{for} \quad 0\leq i\leq n+1\}$$ Write each integer $0\leq i\leq 2^n-1$ in binary as an $n$-digit $0-1$ code. For any $0-1$ code $\alpha$ we process it the following way: If it ends with $1$, we delete the $1$; otherwise we either delete the $0$ at the end, or we change the last $1$ to $0$, then delete $0$ at the end. Observe that this fashion of deleting actually represents $2n+1 \to n$ as well as $2n \to n$ and $2n \to n-2^e$. For each element of $\{0,1\}^n$ we delete it as stated, after $n$ steps it would be fully redacted. Write the $n$ $0-1$ codes in the progress from right to left. We claim that $c_i$ equals to the number of different ways that the binary code of $i$ can be deleted. The claim is easily proved with induction. Now all we have to do is to find a bijection between $X$ and the ways to delete all $n$-digit codes $\mathcal{C}$. Instead of looking at the ways the codes are getting deleted, we look at how that are constructed. It is easy to see that the way of constructing is as follow: First start with nothing (step $0$). In each step, we either put a $0$ at the end, or we put a $1$ anywhere after the last $1$. Keep adding $0$ or $1$ until we reach $n$ digits. Now given a method of constructing $\Sigma\in \mathcal{C}$, in step $i$ there are $h_i$ zeros at the end of the code for $1\leq k\leq n$. We consider the vector $\Psi(\Sigma):=(0,1-h_1,2-h_2,\dots,n-h_n, n+1)$. It is not so hard to check that $\Psi: \mathcal{C}\to X$ is a bijection. Hence the equality is proved.