In this post, we prove the closed form of a nonlinear recurrence corresponding to the count of binary trees with nodes.
Currently Browsing
Posts Tagged ‘ algebra ’
Counting Binary Trees (The Hard Way)
Counting Words
Suppose that we are given the alphabet ; a word of length
:
, is an ordered
-tuple whose elements all came from
. For example, a word of length
in
might be the tuple
, which we will hereon denote as
. For some natural number
, how many words of length
are there that contains exactly
zeros?
Annoying Mclaurin Series
Suppose that we’re given the function , find the ordinary generating function associated with it in the form of
. Furthermore, find/compute
.
Even Pascals
Let , where k is an integer. Prove that for any positive integer n the number
is divisible by .
Sequences in Sequences
Define the sequence recursively by
and
Find an explicit formula for in terms of n.
More Linear Recurrences
Let be defined by the recurrence relation
, with
. Show that the expression
depends only on b and
, but not on a.
Almost Linear
Find the general term of the sequence given by , and
Polynomial Divisors
Let . Show that for any positive integers
there exists unique numbers
such that the polynomial
is divisible by p(x)
Analytical Fibonacci
We derive Binet’s equation for the nth Fibonacci number as
Linear Recursive Sequence
We derive a general technique for solving full rank linear recursive sequences. Formally, a kth linear recursive sequence is defined as