New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Discrete Structures

by: Tony Davis

Discrete Structures ENGR 213

Tony Davis
Christopher Newport University
GPA 3.82

Dali Wang

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Dali Wang
Class Notes
25 ?




Popular in Course

Popular in Engineering and Tech

This 17 page Class Notes was uploaded by Tony Davis on Monday October 5, 2015. The Class Notes belongs to ENGR 213 at Christopher Newport University taught by Dali Wang in Fall. Since its upload, it has received 6 views. For similar materials see /class/219482/engr-213-christopher-newport-university in Engineering and Tech at Christopher Newport University.

Similar to ENGR 213 at Christopher Newport University

Popular in Engineering and Tech


Reviews for Discrete Structures


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/05/15
Solving Recurrence Relations Section 62 of the Text Review nth degree polynomials have n roots an x an1x 391 alx a0 O If the coefficients are real then the roots are real or occur in complex conjugate pairs Recall the quadratic formula ax2 bx C 0 then xZ bim 2a Solving Recurrence Relations Review We assume you remember how to solve linear systems AX b where A is an n x n matrix Example Solving Recurrence Relations Statement of the Problem aga 9 agn1 a form or an express10n for a gm Example fn 3n lt gt f01fn 3fn1 Solving Recurrence Relations Form of Recurrence Equations Solving recurrence relations can be very difficult unless the recurrence equation has a special form gn n single variable the equation is linear sum of previous terms no transcendental functions of the aquot s o no products of the ai s constant coefficients the coefficients in the sum of the a s are constants independent of n Solving Recurrence Relations 5 Form of Recurrence Equations cont unless the recurrence equation has a special form degree k an is a function of only the previous k terms in the sequence homogeneous If we put all the a39s on one side of the equation and everything else on the right side then the right side is O OthenNise inhomogeneous or nonhomogeneous Solving Recurrence Relations Form of Recurrence Equations cont A recurrence relation an fan1 ank has degree k if the function f depends on the term ank and if it depends on no terms of lower index It is linear of degree k if it has the form an Clanl CZanZ Ckank Where each ck is a real function and ok 72 0 It is homogenous if gn 0 Solving Recurrence Relations Examples linear const homo degree coef geneous an 2 1 02an1 an 102an1 2n1 an 2 an1 aw am3 2n393 an 2 canm b 2 an nan1 n an2 an lan Z Solving Recurrence Relations Solving Recurrence Equations A linear mmogeneous currence of degree llt with Qnstant Qef cients kLiHoReCoCo is a reccurrence relation of the form an c1aa1 ckank where the c are all real and ckq O The solution is uniquely determined if k initial conditions a0ak1 are provided Solving Recurrence Relations Solution Procedure Equation kLiHoReCoCo an Clan1 CZaHZ o o o Ckank Steps 1 Put all ai39s on the left side of the equation everything else on the right If nonhomogeneous stop for now an c1an1 02am2 ckank O 2 Assume a solution of the form an bquot Substitute the solution into the equation factor out the lowest power of b and eliminate it b 0119 Czbn392 ckb 39k O bn39kbk clbk391 ck 0 Solving Recurrence Relations 10 Solution Procedure cont Steps 3 The remaining polynomial of degree k bk clbk 1 ck is called the characteristic polynomial The corresponding equation is called characteristic equa on Find its k roots r1 r2 rk 4 If the roots are distinct the general solution is an owl 0c2r2 ockrk Solving Recurrence Relations 11 Solution Procedure cont Steps 5 The coefficients a1 a2 ak are found by enforcing the initial conditions Solve the resulting linear system of equations a0 0L1r10 0L2r20 Ockrk0 a1 0L1r11 0L2r21 Ockrk1 ak l Ollrlk 391 ourzk 391 0Lkrkk 391 Solving Recurrence Relations 12 Examples Solving the recurrence equation an 3an1aO 4 Solution Step 1 Bring subscripted variables to one side an3an1 O Step 2 Substitute an bn and factor lowest power of b bn391b3 O or b3 O Step 3 Find the root of the characteristic equation r1 3 Solving Recurrence Relations 13 Examples cont Solution cont Step 4 Compute the general solution an c3n Step 5 Find the constants based on the initial conditions 210 C30 or c 4 Finally Produce the specific solution an 43 Solving Recurrence Relations 14 Examples Solving the recurrence equation an3a n2 a0 2 a1 2 1 Solving Recurrence Relations The Case of Degenerate Roots If a root r1 has multiplicity p then the solution corresponding the root is oc1 oc2n ocpnp391r1 For quadratic case if the characteristic equation r2 c1r 02 O has only 1 root r0 then an 01r0 aznro for all n20 for some constants a1 a2 Solving Recurrence Relations Examples Solving the recurrence equation an 2 6an1 9a n Z aOZalzl Solving Recurrence Relations


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Amaris Trozzo George Washington University

"I made $350 in just two days after posting my first study guide."

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.