Patrick B.

Give a closed formula for C(n).

C(n) = 1/(n+1) * nCr(2n, n)

Give a Recurrence Relation for the Catalan Numbers involving a Summation.

C(0) = 1,

C(n+1) = Sum(i=0, n, C(i)*C(n-i))

for n >= 0.

C(n+1) = Sum(i=0, n, C(i)*C(n-i))

for n >= 0.

Advertisement

Give a Recurrence Relation for the Catalan Numbers NOT involving a Summation.

C(0) = 1,

C(n+1) = 2*(2n+1) / (n+2) * C(n)

C(n+1) = 2*(2n+1) / (n+2) * C(n)

In terms of the Fibonacci Numbers, What is Pascal's Relation?

Prove by showing h(n) = h(n-1) + h(n-2).

Prove by showing h(n) = h(n-1) + h(n-2).

for N>=1,

F(n) = Sum(k=0, n-1,

nCr(n-k-1, k))

F(n) = Sum(k=0, n-1,

nCr(n-k-1, k))

Give the Recurrence Relation for the Fibonacci Numbers.

What type of linear recurrence relation?

What type of linear recurrence relation?

F(0) = 0, F(1) = 1,

F(n) = F(n-1) + F(n-2)

This is a "Second Degree" Linear Recurrence Relation.

F(n) = F(n-1) + F(n-2)

This is a "Second Degree" Linear Recurrence Relation.

Give an exact formula for the Fibonacci Numbers.

F(n) = 1/sqrt(5) * ( ( (1+sqrt(5))/2 )^n - ( (1-sqrt(5))/2 )^n )

Give the Generating Function for the Fibonacci Numbers.

Sum(n=0, infinity, F(n+1)*x^n) =

1 / (1 - x - x^2)

1 / (1 - x - x^2)

Define a K-term Linear Recurrence Relation.

Any sequence of complex numbers {r(n)} with the property that

r(n) = a(1)*r(n-1) + a(2)*r(n-2) + ... + a(k)*r(n-k)

Where a(k) Does not equal 0, and r(0), r(1), ..., r(k-1) are predetermined.

r(n) = a(1)*r(n-1) + a(2)*r(n-2) + ... + a(k)*r(n-k)

Where a(k) Does not equal 0, and r(0), r(1), ..., r(k-1) are predetermined.

Give the general generating function for a K-term Linear Recurrence Relation.

Sum(n=0, infinity, r(n)*x^n) =

Sum(i=1, k, gamma(i)/ (1-alpha(i)*x))

Sum(i=1, k, gamma(i)/ (1-alpha(i)*x))

Explain how to solve a homogeneous linear recurrence relation.

1) Find the characteristic roots by solving the characteristic equation:

x^n = a(n-1)*x^(n-1) + ... + a(0)

(a(0) =/ 0 so x=0 is not a root.)

2) Use these roots to solve along with initial values:

r(n) = gamma(1)*alpha(1)^n + gamma(2)*alpha(2)^n + ... + gamma(k)*alpha(k)^n

x^n = a(n-1)*x^(n-1) + ... + a(0)

(a(0) =/ 0 so x=0 is not a root.)

2) Use these roots to solve along with initial values:

r(n) = gamma(1)*alpha(1)^n + gamma(2)*alpha(2)^n + ... + gamma(k)*alpha(k)^n

Explain how to solve a non-homogeneous, non-linear recurrence relation.

1) Assume homogeneity, solve the characteristic equation.

2) The final solution must be of the form:

r(n) = Sum(i=1, k, gamma(i)*alpha(i)^n) + F(hat)(n)

3) Solve for F(hat)(n) Satisfying the original recurrence. F(hat)(n) is of the form A*n^2 + B*n + C. Solve for A, B, C.

2) The final solution must be of the form:

r(n) = Sum(i=1, k, gamma(i)*alpha(i)^n) + F(hat)(n)

3) Solve for F(hat)(n) Satisfying the original recurrence. F(hat)(n) is of the form A*n^2 + B*n + C. Solve for A, B, C.

Advertisement

Give the recurrence relation for the Derangement Sequence.

For n >= 3, d(n) =

(n-1)[d(n-1) + d(n-2)]

d(1) = 0, d(2) = 1

This Recurrence follows from the generating function.

(n-1)[d(n-1) + d(n-2)]

d(1) = 0, d(2) = 1

This Recurrence follows from the generating function.

What Proportion of Permutations are Derangements?

lim n=>infinity d(n)/n! =

lim n=>infinity n!/n! * Sum(k=0, n,

(-1)^k/k!) = 1/e, by taylor series of e^-x where x=1.

So ~~ .3678

lim n=>infinity n!/n! * Sum(k=0, n,

(-1)^k/k!) = 1/e, by taylor series of e^-x where x=1.

So ~~ .3678

Give the Generating Function for the Derangement Sequence.

If n is a positive integer, then

d(n) = n!*(1 - 1/1! + 1/2! - ... +

(-1)^n*1/n!) =

n! * Sum(k=0, n, (-1)^k / k!).

This follows from the inclusion-exclusion principle.

d(n) = n!*(1 - 1/1! + 1/2! - ... +

(-1)^n*1/n!) =

n! * Sum(k=0, n, (-1)^k / k!).

This follows from the inclusion-exclusion principle.

Give the General Form of a generating function.

1 / (1-alpha*x) = Sum(n=0, infinity, alpha^n*x^n)

The End

The End

"The semester I found StudyBlue, I went from a 2.8 to a 3.8, and graduated with honors!"

Jennifer Colorado School of Mines
StudyBlue is not sponsored or endorsed by any college, university, or instructor.

© 2015 StudyBlue Inc. All rights reserved.

© 2015 StudyBlue Inc. All rights reserved.