# Exam 3:

**Created:**2009-01-25

**Last Modified:**2011-07-03

#### Related Textbooks:

Introductory Combinatorics (5th Edition)C(n+1) = Sum(i=0, n, C(i)*C(n-i))

for n >= 0.

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

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

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

nCr(n-k-1, k))

What type of linear recurrence relation?

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

This is a "Second Degree" Linear Recurrence Relation.

1 / (1 - x - x^2)

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.

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

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

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.

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

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

This Recurrence follows from the generating function.

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

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.

#### Words From Our Students

"StudyBlue is great for studying. I love the study guides, flashcards, and quizzes. So extremely helpful for all of my classes!"

Alice, Arizona State University

"I'm a student using StudyBlue, and I can 100% say that it helps me so much. Study materials for almost every subject in school are available in StudyBlue. It is so helpful for my education!"

Tim, University of Florida

"StudyBlue provides way more features than other studying apps, and thus allows me to learn very quickly! I actually feel much more comfortable taking my exams after I study with this app. It's amazing!"

Jennifer, Rutgers University

"I love flashcards but carrying around physical flashcards is cumbersome and simply outdated. StudyBlue is exactly what I was looking for!"

Justin, LSU