0
votes
1answer
42 views

Recursive trees

Use the method of recursive tree to determine a good asymptotic upper bound (as tight as possible) for the following recurrence and prove your answer using induction (assuming that $T(n)$ is a ...
6
votes
4answers
194 views

Recursive Sequence Tree Problem (Original Research in the Field of Comp. Sci)

This question appears also in http://cstheory.stackexchange.com/questions/17953/recursive-sequence-tree-problem-original-research-in-the-field-of-comp-sci. I was told that cross-posting in this ...
3
votes
0answers
66 views

Recurrence relation induction [duplicate]

Possible Duplicate: Solving the recurrence $t(n)=(t(n-1))^2 + 1$ Show that the number of binary trees of height less than or equal to $n$ is given by the recurrence \begin{align*} ...
2
votes
1answer
94 views

Showing two recurrences to be identical

I am trying to prove Cayley's formula for number of labelled trees on n vertices using multinomial coefficients. The multinomial coefficient satisfies the recurrence: $\tbinom{n}{r_1,\cdots ...