Definition. A binary tree is either empty, or consists of a vertex called the root, plus an ordered pair of binary trees called the left-subtree and right-subtree.
For each n ∈ N n \in \mathbb{N} n ∈ N b n b_n b n n n n
Theorem. For all n ∈ N n \in \mathbb{N} n ∈ N
b n = 1 1 + n ⋅ ( 2 n n ) .
b_n = \frac{1}{1 + n} \cdot \binom{2 n}{n}.
b n = 1 + n 1 ⋅ ( n 2 n ) .
Proof.
When n = 0 n = 0 n = 0 b 0 = 1 = 1 1 + 1 ( 2 1 ) b_0 = 1 = \frac{1}{1 + 1} \binom{2}{1} b 0 = 1 = 1 + 1 1 ( 1 2 )
For all n ≥ 1 n \ge 1 n ≥ 1
b n = ∑ k = 0 n − 1 b k ⋅ b n − 1 − k .
b_n = \sum_{ k = 0 }^{n - 1} b_k \cdot b_{n - 1 - k}.
b n = k = 0 ∑ n − 1 b k ⋅ b n − 1 − k . Define the generating function of ( b 0 , b 1 , … ) (b_0, b_1, \ldots ) ( b 0 , b 1 , … )
b ( x ) ≐ b 0 + b 1 x + b 2 x 2 + …
b(x) \doteq b_0 + b_1 x + b_2 x^2 + \ldots
b ( x ) ≐ b 0 + b 1 x + b 2 x 2 + … It holds that b n b_n b n x n − 1 x^{n - 1} x n − 1 b ( x ) ⋅ b ( x ) b(x) \cdot b(x) b ( x ) ⋅ b ( x ) x n x^n x n x ⋅ b ( x ) ⋅ b ( x ) x \cdot b(x) \cdot b(x) x ⋅ b ( x ) ⋅ b ( x )
b ( x ) = b 0 + x ⋅ ( b ( x ) ) 2 = 1 + x ⋅ ( b ( x ) ) 2 .
b(x) = b_0 + x \cdot (b (x) )^2 = 1 + x \cdot (b (x) )^2.
b ( x ) = b 0 + x ⋅ ( b ( x ) ) 2 = 1 + x ⋅ ( b ( x ) ) 2 . There are two possible closed form solution for b ( x ) b(x) b ( x )
b ( x ) = 1 ± 1 − 4 x 2 x .
b(x) = \frac{ 1 \pm \sqrt{1 -4 x} }{ 2 x }.
b ( x ) = 2 x 1 ± 1 − 4 x . As b ( 0 ) = b 0 = 1 b(0)= b_0 = 1 b ( 0 ) = b 0 = 1 ( 1 + 1 − 4 ⋅ 0 ) / ( 2 ⋅ 0 ) = ∞ (1 + \sqrt{1 - 4 \cdot 0} ) / (2 \cdot 0) = \infty ( 1 + 1 − 4 ⋅ 0 ) / ( 2 ⋅ 0 ) = ∞
b ( x ) = 1 − 1 − 4 x 2 x .
b(x) = \frac{ 1 - \sqrt{ 1 - 4 x} }{ 2 x }.
b ( x ) = 2 x 1 − 1 − 4 x . The Taylor's expansion 1 − 4 ⋅ x \sqrt{1 - 4 \cdot x} 1 − 4 ⋅ x x = 0 x = 0 x = 0
1 − 4 ⋅ x = 1 + ( 1 / 2 1 ) ⋅ ( 4 x ) + ( 1 / 2 2 ) ⋅ ( 4 x ) 2 + . . . = ∑ k ∈ N ( 1 / 2 k ) ( − 4 ) k x k .
\begin{aligned}
\sqrt{1 - 4 \cdot x}
&= 1 + \binom{1 / 2}{1} \cdot (4x) + \binom{1 / 2}{2} \cdot (4x)^2 + ... \\
&= \sum_{k \in \mathbb{N}} \binom{1 / 2}{ k } (-4)^k x^k.
\end{aligned}
1 − 4 ⋅ x = 1 + ( 1 1/2 ) ⋅ ( 4 x ) + ( 2 1/2 ) ⋅ ( 4 x ) 2 + ... = k ∈ N ∑ ( k 1/2 ) ( − 4 ) k x k . where
( 1 / 2 k ) ≐ ( 1 / 2 ) ⋅ ( 1 / 2 − 1 ) ⋅ ( 1 / 2 − 2 ) … ⋅ ( 1 / 2 − k + 1 ) k ! .
\binom{1 / 2}{ k } \doteq \frac{ (1 / 2) \cdot (1 / 2 - 1) \cdot (1 /2 - 2) \ldots \cdot (1 / 2 - k + 1) }{ k! }.
( k 1/2 ) ≐ k ! ( 1/2 ) ⋅ ( 1/2 − 1 ) ⋅ ( 1/2 − 2 ) … ⋅ ( 1/2 − k + 1 ) . We conclude that
b ( x ) = ∑ k ∈ N ( − 1 2 ) ⋅ ( 1 / 2 k + 1 ) ( − 4 ) k + 1 x k .
b(x) = \sum_{k \in \mathbb{N} } \left( -\frac{1}{2} \right) \cdot \binom{1 / 2}{k + 1} (-4)^{k + 1} x^k.
b ( x ) = k ∈ N ∑ ( − 2 1 ) ⋅ ( k + 1 1/2 ) ( − 4 ) k + 1 x k . From this, we can also verify that ( 1 − 1 − 4 x ) / ( 2 x ) = 1 (1 - \sqrt{ 1 - 4 x} ) / ( 2 x ) = 1 ( 1 − 1 − 4 x ) / ( 2 x ) = 1
Finally, for k ≥ 1 k \ge 1 k ≥ 1
( − 1 2 ) ⋅ ( 1 / 2 k + 1 ) ⋅ ( − 4 ) k + 1 = ( − 1 2 ) ⋅ ( 1 / 2 − k ) ⋅ ( 1 / 2 − k + 1 ) ⋅ . . . ⋅ ( − 1 / 2 ) ⋅ ( 1 / 2 ) ( k + 1 ) ! ⋅ ( − 4 ) k + 1 = ( 1 / 2 − k ) ⋅ ( 1 / 2 − k + 1 ) ⋅ . . . ⋅ ( − 1 / 2 ) ( k + 1 ) ! ⋅ ( − 4 ) k = ( 2 k − 1 ) ⋅ ( 2 k − 3 ) ⋅ . . . ⋅ 1 ( k + 1 ) ! ⋅ 2 k = ( 2 k ) ! ( k + 1 ) ! ⋅ k ! ⋅ 2 k ⋅ 2 k = 1 k + 1 ( 2 k k ) .
\begin{aligned}
&\left( -\frac{1}{2} \right) \cdot \binom{1 / 2}{k + 1} \cdot ( -4 )^{k + 1} \\
=& \left( -\frac{1}{2} \right) \cdot \frac{ (1 / 2 - k) \cdot (1 / 2 - k + 1) \cdot ... \cdot (- 1 / 2) \cdot (1 / 2) }{ (k + 1)! } \cdot ( -4 )^{k + 1} \\
=& \frac{ (1 / 2 - k) \cdot (1 / 2 - k + 1) \cdot ... \cdot (- 1 / 2) }{ (k + 1)! } \cdot ( -4 )^{k} \\
=& \frac{ (2k - 1) \cdot (2k - 3) \cdot ... \cdot 1 }{ (k + 1)! } \cdot 2^k \\
=& \frac{ (2k)! }{ (k + 1)! \cdot k! \cdot 2^k } \cdot 2^k \\
=& \frac{1}{k + 1} \binom{2k}{k}.
\end{aligned}
= = = = = ( − 2 1 ) ⋅ ( k + 1 1/2 ) ⋅ ( − 4 ) k + 1 ( − 2 1 ) ⋅ ( k + 1 )! ( 1/2 − k ) ⋅ ( 1/2 − k + 1 ) ⋅ ... ⋅ ( − 1/2 ) ⋅ ( 1/2 ) ⋅ ( − 4 ) k + 1 ( k + 1 )! ( 1/2 − k ) ⋅ ( 1/2 − k + 1 ) ⋅ ... ⋅ ( − 1/2 ) ⋅ ( − 4 ) k ( k + 1 )! ( 2 k − 1 ) ⋅ ( 2 k − 3 ) ⋅ ... ⋅ 1 ⋅ 2 k ( k + 1 )! ⋅ k ! ⋅ 2 k ( 2 k )! ⋅ 2 k k + 1 1 ( k 2 k ) . □ \square □
Remark: We reach an interesting equality that
( ( 2 k − 1 ) ⋅ ( 2 k − 3 ) ⋅ … ⋅ 1 ) ⋅ 2 k = ( 2 k ) ⋅ ( 2 k − 1 ) ⋅ … ⋅ ( k + 1 ) .
\Big( (2k - 1) \cdot (2k - 3) \cdot \ldots \cdot 1 \Big) \cdot 2^k = (2k) \cdot (2k - 1) \cdot \ldots \cdot (k + 1).
( ( 2 k − 1 ) ⋅ ( 2 k − 3 ) ⋅ … ⋅ 1 ) ⋅ 2 k = ( 2 k ) ⋅ ( 2 k − 1 ) ⋅ … ⋅ ( k + 1 ) . Reference
[1] J. Matoušek and J. Nešetřil, Invitation to discrete mathematics, 2nd ed. Oxford ; New York: Oxford University Press, 2009.
← Back to all notes Back to top ↑