Share
Explore BrainMass

Recurrence Relation

Relations : Properties and Equivalence Classes

Please see the attached file for the fully formatted problem. Exercise 5 (4p) R is the relation defined on Z ts follows: for all m,n E Z, m R n <=>4|(m-n) a. Determine whether the relaition is reflexive. b. Determine whether the relation is symmetric. c. Determine whether the relation is transitive. d. In case the relat

Catalan Numbers

Prove recurrence relationship of Catalan Numbers. Question: Let n be a non-negative integer. The number, x[n], of topologically distinct binary trees with n nodes can be shown to satisfy the following recurrence (x[0] = 1): See attached file for full problem description.

Mathematical Induction

Prove that the Fibonacci sequence can be obtained by the recurrence relationship. See attached file for full problem description.

Fibonacci sequence in closed form

Prove that Fn can be expressed by: Fn=[(a^n-b^n)/(a-b)] for n=1,2,3... ~: Set Gn=[(a^n-b^n)/(a-b)] and show that Gn satisfies the recurrence formula {G(n+1) = Gn + G(n-1) for n=2,3,4...} and don't forget that a and b satisfy the equation x^2-x-1=0. a and b are the roots of x^2-x-1=0, which are (1+sqrt5)/2 and (1-sqrt5)/2

Discrete Structures

1. Consider the sequence of triangles Ti, i >= 2: T2 is simply a triangle sitting upright, on its base. T3 is T2, except that an additional straight line is drawn from the upper vertex, down to somewhere on the base. For each Ti+1, one more line is added to triangle Ti (such that each line meets the base at a different point).