Counting Binary Trees (The Hard Way)

In this post, we prove the closed form of a nonlinear recurrence corresponding to the count of binary trees with $n$ nodes.

9 November

Posted in Article, Math Problems

0

Counting Words

Suppose that we are given the alphabet $\Sigma = \Rec{0,1,2}$ ; a word of length $n$ : $x_n \in \Sigma^5$ , is an ordered $n$ -tuple whose elements all came from $\Sigma$ . For example, a word of length $5$ in $\Sigma$ might be the tuple $(0,0,2,1,0)$ , which we will hereon denote as $00210$ . For some natural number $k \le n$ , how many words of length $n$ are there that contains exactly $k$ zeros?

6 November

Posted in Article, Math Problems, Numerical Analysis

5

Annoying Mclaurin Series

Suppose that we’re given the function $B(z) = \frac{1 + z}{1 - z - z^2}$ , find the ordinary generating function associated with it in the form of $B(z) = \sum_{k=0}^\infty b_k k^z$ . Furthermore, find/compute $\sigma_n = \sum_{k=0}^n b_k$ .

14 August

Posted in Article, Math Problems

0

Even Pascals

Let $a=4k-1$ , where k is an integer. Prove that for any positive integer n the number

$s_n = 1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3 + \cdots$

is divisible by $2^{n-1}$ .

14 August

Posted in Article, Math Problems

0

Sequences in Sequences

Define the sequence $(a_n)_n$ recursively by $a_1 = 1$ and

$a_{n+1} = \frac{1 + 4a_n + \sqrt{1+24a_n}}{16} ,\hspace{4mm} \mbox{for $n \ge 1$.}$

Find an explicit formula for $a_n$ in terms of n.

14 August

Posted in Article, Math Problems

0

More Linear Recurrences

Let $(x_n )_n = 0$ be defined by the recurrence relation $x_{n + 1} = ax_n + bx_{n - 1}$ , with $x_0 = 0$ . Show that the expression $x^2_n - x_{n - 1} x_{n + 1}$ depends only on b and $x_1$ , but not on a.

13 August

Posted in Article, Math Problems

0

Almost Linear

Find the general term of the sequence given by $x_0 = 3, x_1 = 4$ , and

$(n + 1 )(n + 2 )x_n = 4 (n + 1 )(n + 3 )x_{n - 1} - 4 (n + 2 )(n + 3 )x_{n - 2}$

13 August

Posted in Article, Math Problems

0

Polynomial Divisors

Let $p(x) = x^2 -3x + 2$ . Show that for any positive integers $n \ge 2$ there exists unique numbers $a_n, b_n$ such that the polynomial $x^n - a_n x - b_n$ is divisible by p(x)