Intereting Posts

Integral $\int \sqrt{x+\sqrt{x^2+2}}dx$
Evaluating an integral across contours: $\int_C\text{Re}\;z\,dz\,\text{ from }-4\text{ to } 4$
Proof that $\frac{2}{3} < \log(2) < \frac{7}{10}$
Legendre Polynomials: proofs
calculating $a^b \!\mod c$
How to write special set notation by hand?
Help to understand material implication
All real functions are continuous
Why is $1/i$ equal to $-i$?
Eigenvalues of the sum of two negative definite matrices with real eigenvalues
Integrating $ \int_0^2 \int_0^ \sqrt{1-(x-1)^2} \frac{x+y}{x^2+y^2} dy\,dx$ in polar coordinates
Disjoint closed sets in a second countable zero-dimensional space can be separated by a clopen set
Can't argue with success? Looking for “bad math” that “gets away with it”
If $A^kX=B^kY$ for all $k$, is $X=Y$?
If $f\in L^1(\mathbb{R})$ is such that $\int_{\mathbb{R}}f\phi=0$ for all continuous compactly supported $\phi$, then $f\equiv 0$.

$$C_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor}{n\choose 2k}\cdot C_k\cdot 2^{n-2k}$$

where $C_n$ are the Catalan numbers.

I think we start by diving both sides by $2^n$, but unsure of where to go from there

- Harmonic Numbers series I
- How to show $\binom{2p}{p} \equiv 2\pmod p$?
- Closed form for $ S(m) = \sum_{n=1}^\infty \frac{2^n \cdot n^m}{\binom{2n}n} $ for integer $m$?
- Catalan's constant and $\int_{0}^{2 \pi} \int_{0}^{2 \pi} \ln(\cos^{2} \theta + \cos^{2} \phi) ~d \theta~ d \phi$
- Prove this recurrence relation? (catalan numbers)
- Cashier has no change… catalan numbers.. probability question

- Partition an integer $n$ into exactly $k$ distinct parts
- Number of digits from $1$ to $n$
- Give a combinatorial proof: $ n(n+1)2^{n-2} = \sum_{k=1}^{n}k^2\binom{n}{k} $
- How can I find the number of the shortest paths between two points on a 2D lattice grid?
- Nested summations and their relation to binomial coefficients
- Number of squares in $n\times n$ chessboard
- How can we show that 3-dimensional matching $\le_p$ exact cover?
- Proving a combinatorics equality: $\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}$
- Count the number of paths from $(0,0)$ to $(2n,n)$ than never go above $y=x$
- Finding Expressively Adequate truth Functions

Notice that $2^{-2k}\binom{n}{2k}\binom{2k}{k}=\binom{n/2}{k}\cdot \binom{n/2-1/2}{k}$. So

$$A_n=\sum_{k=0}^{\lfloor n/2 \rfloor}2^n \cdot 2^{-2k}\cdot \binom{n}{2k}\binom{2k}{k}\cdot\dfrac{1}{k+1}=2^n\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n/2}{k}\cdot \binom{n/2-1/2}{k}\cdot\dfrac{1}{k+1}$$

Without loss of generality, suppose $n/2 \in \mathbb{N}$. By Vandermonde’s identity, we have

$$A_n=\dfrac{2^n}{n/2+1} \cdot \binom{n+1/2}{n/2}=\dfrac{1}{n+2}\binom{2(n+1)}{n+1}=C_{n+1}$$

Here is a proof using the method by Wilf from

*Generatingfunctionology.*

Suppose we are trying to show that

$$C_{n+1} = 2^n \sum_{k=0}^{\lfloor n/2 \rfloor}

{n\choose 2k} C_k 2^{-2k}$$

where $C_n = \frac{1}{n+1}{2n\choose n}$ is the $n$-th Catalan number.

Recall the Catalan number recurrence

$$C_{n+1} = \sum_{k=0}^n C_k C_{n-k}$$

which implies for the generating function $C(z)$ of these numbers that

$$\frac{C(z)-1}{z} = C(z)^2$$

which has solutions $$C_{1,2}(z) = \frac{1\pm \sqrt{1-4z}}{2z}$$

of which the second one is analytic at zero so that

$$C(z) = \frac{1- \sqrt{1-4z}}{2z}.$$

Following Wilf we introduce the generating function $D(z)$ where

$$D(z) = \sum_{n\ge 0} z^n 2^n

\sum_{k=0}^{\lfloor n/2 \rfloor}

{n\choose 2k} C_k 2^{-2k}

= \sum_{k\ge 0} C_k 2^{-2k}

\sum_{n\ge 2k} {n\choose 2k} z^n 2^n

\\ = \sum_{k\ge 0} C_k 2^{-2k}

\sum_{n\ge 0} {n+2k\choose 2k} z^{n+2k} 2^{n+2k}

= \sum_{k\ge 0} C_k z^{2k}

\sum_{n\ge 0} {n+2k\choose 2k} z^n 2^n

\\ = \sum_{k\ge 0} C_k z^{2k} \frac{1}{(1-2z)^{2k+1}}.$$

This gives that

$$D(z) = \frac{1}{1-2z}

\frac{1-\sqrt{1-4z^2/(1-2z)^2}}{2z^2/(1-2z)^2}

\\ = \frac{(1-2z)^2}{1-2z}

\frac{1-\sqrt{1-4z^2/(1-2z)^2}}{2z^2}

= (1-2z)

\frac{1-\sqrt{1-4z^2/(1-2z)^2}}{2z^2}

\\= \frac{1-2z-\sqrt{(1-2z)^2-4z^2}}{2z^2}

= \frac{1-2z-\sqrt{1-4z}}{2z^2}.$$

On the other hand

$$\sum_{n\ge 0} C_{n+1} z^n

= \frac{C(z)-1}{z}

= \frac{1}{z} \left(\frac{1- \sqrt{1-4z}}{2z} -1 \right)

\\ = \frac{1}{z} \left(\frac{1- 2z -\sqrt{1-4z}}{2z}\right)

= \frac{1- 2z -\sqrt{1-4z}}{2z^2}.$$

We have equality, QED.

- Using generating functions to find a formula for the Tower of Hanoi numbers
- Does homotopy equivalence of pairs $f:(X,A)\to(Y,B)$ induce the homotopy equivalence of pairs $f:(X,\bar A)\to(Y,\bar B)$?
- $z_0$ non-removable singularity of $f\Rightarrow z_0$ essential singularity of $\exp(f)$
- Alternate definition of prime number
- Is always possible to find a generalized eigenvector for the Jordan basis M?
- Convergence Problem.
- Prove the uniqueness of poisson equation with robin boundary condition
- Expressing the roots of a cubic as polynomials in one root
- Why $\mathrm e^{\sqrt{27}\pi } $ is almost an integer?
- drawing at least one colored ball of each from urn in a case of large populations
- How do I show a particular polynomial has Galois group $Z_3$?
- The norm and the spectrum of $B(L^p(X,\mu))$
- Solve $x = \frac{1}{2}\tan(x)$
- Show that the rank of $A+B$ is no more than the sum of th ranks of $A$ and $B$
- What are the properties of the fourier transform of a phase-only function?