[PDF] Discrete Mathematics II (Spring 2015) - 8.2 Solving Linear





Previous PDF Next PDF



CS 161 Lecture 3 - 1 Solving recurrences

Last class we introduced recurrence relations such as T(n) = 2T(?n/2?) + n. Typically Here a = 9



Discrete Mathematics II (Spring 2015) - 8.2 Solving Linear

Determine what is the degree of the recurrence relation. • Need to know the general solution equations. • Need to find characteristic equation. • Need to find 



Recurrences

n = 2k for some constant k and leaving out base case and constant in ?). Methods for solving recurrences. 1. Substitution method. 2. Iteration method.



Q1: Exercise 2.3-3 (10 points) Use mathematical induction to show

recurrence. T(n) =2 ifn=2. 2T(n/2) + n if n = 2k for k > 1 is T(n) = n logn. . Base Step: If n = 2



Master Theorem: Practice Problems and Solutions

The Master Theorem applies to recurrences of the following form: 2. T(n)=4T(n/2) + n2. 3. T(n) = T(n/2) + 2n. 4. T(n)=2nT(n/2) + nn.



GENERATING FUNCTIONS AND RECURRENCE RELATIONS

A recurrence recurrence relation is a set of equations Linear Recurrence. Fibonacci Sequence an = an?1 + an?2 n ? 2. ... n=2 n(n ? 1)xn +.



Solving Recurrences

For example the following recurrence (written in two different but standard ways) describes the identity function f (n) = n:.



1.1 Time complexity and Big-Oh notation: exercises

2. A quadratic algorithm with processing time T(n) = cn2 spends T(N) To have the well-defined recurrence assume that n = km with the integer.



Sample Induction Proofs

(?1)nn(n + 1). 2 . Base case: When n = 1 the left side of (1) is (?1)12 = ?1



3. Recurrence 3.1. Recursive Definitions. To construct a recursively

Example 3.2.1. The factorial function f(n) = n! is defined recursively as follows: 1. Initial Condition: f(0) = 1. 2. Recursion: f(n +1)=(n + 1)f(n).



Recurrence Relations - Hong Kong University of Science and

an= 2 n¡1; n ‚1: Given a recurrence relation for a sequence with initial conditions Solving the recurrence relation means to ?nd a formula to express the general termanof the sequence 2 Homogeneous Recurrence Relations Any recurrence relation of the form



Solving Recurrence Relations - Texas A&M University

n 2 and the base cases of the induction proof (which is not the same as the base case of the recurrence!) are n= 2 and n= 3 (We are allowed to do this because asymptotic notation only requires us to prove our statement for n n 0 and we can set n 0 = 2 ) We choose n= 2 and n= 3 for our base cases because when we expand the recurrence



Recurrence Relations - University of Ottawa

Many sequences can be a solution for the same recurrence relation a n = 2a n 1 a n 2; for n 2 The following sequences are solutions of this recurrence relation: I a n = 3n for all n 0 I a n = 5 for all n 0 The initial conditions for a sequence specify the terms before n 0 (before the recurrence relation takes e ect)



Solving Recurrence Relations - Princeton University

n 2 to be C0 and C1 Since the sequences fang and f 1rn 1 + 2r n 2g satisfy the degree 2 recurrence and agree on the rst two values they must be identical Example: Find the solution to the recurrence relation an = an 1 +an 2 with initial condi-tions a0 = 2 and a1 = 7 Solution: The characteristic equation is r2 r 2 = 0 i e (r 2)(r +1) = 0



Recurrence Relations - University of Illinois Urbana-Champaign

2 Recall that 1=nk= nk and we have rn 2(r25r + 6) = 0 Then we can factor the polynomial into rn 2(r 2)(r 3) = 0 We assumed that r is non-zero so we can divide by the rst factor rn 2 which leaves (r 2)(r 3) = 0 Thus the characteristic function (also: polynomial) remains on the left-hand side



Searches related to 2^n n^2 recurrence PDF

n = 2n for every nonnegative integer n is a solution of the recurrence relation a n = 2a n-1 - a n-2 for n = 234 Assume a 0=1 and a 1=2 Solution: Check initial conditions a 0= 20 = 1 a 1= 2 1 = 2 Check if {2n} satisfies a n = 2a n-1 - a n-2 2a n-1 - a n-2 = 2(2n-1) - 2n-2 = 2n-2(4-1) = 3(2n-2) 2n So {2n} is not a solution for a n = 2a

What is the solution of the recurrence relation?

.Thenasequence (a n ) is a solution of the recurrence relation a n= c 1a n?1+ c 2a n?2 if and only if a n= ? 1r n 1+ ? 2r n 2 for n ? 0 for some constants ? 1,? 2 Idea of the Proof The proof proceeds exactly as in the case of the Fibonacci numbers. Try to prove it yourself!

What is the solution of recurrence relation an = 10an-1 - 25an-2?

The solution of the recurrence relation an = 10an-1 - 25an-2, is: (a0 = 1, a1 = 15) Q8. Solution to recurrence relation T (n) = T (n - 1) + 4 is given by, where n > 0 and T (0) = 3.

What is a 2 nd-order linear recurrence?

This is a subset of the type of 2 nd -order recurrence formulas used by MCS . The Fibonacci number s are the best-known example of a 2 nd -order linear recurrence.

What is the initial condition for a recurrence relation?

So (a_n = 3a_ {n-1} + 2) is our recurrence relation and the initial condition is (a_0 = 1 ext {.}) We are going to try to solve these recurrence relations.

ICS 241: Discrete Mathematics II (Spring 2015)

8.2 Solving Linear Recurrence Relations

Determine if recurrence relation is homogeneous or nonhomogeneous. Determine if recurrence relation is linear or nonlinear. Determine whether or not the coefficients are all constants. Determine what is the degree of the recurrence relation.

Need to know the general solution equations.

Need to find characteristic equation.

Need to find characteristic roots (can use determinant to help).

Determinants (optional)

When finding characteristic roots and determining which general solution to use for a recur- rence relation of degree 2, using determinants can be helpful. From the quadratic equation, x=bpb

24ac2a, the determinant isb24ac.

Case 1:b24ac >0

You have two distinct real roots,r1andr2, your general solution isan=1rn1+2rn2. (Theorem 1)

Case 2:b24ac= 0

You have one root with multiplicity 2,r0, your general solution isan=1rn0+2nrn0. (Theorem 2) Summary of general solutionsTheoremDegreeCharacteristic RootsGeneral Solution 12r

16=r2a

n=1rn1+2rn222r

0with multiplicity 2a

n=1rn0+2nrn03kkdistinct rootsr1;r2;:::;rka n=1rn1+2rn2+:::+krnk4ktdistinct roots (r1;r2;:::rt) with multiplicities(m1;m2;:::;mt)a n= (1;0+1;1n+:::+1;m11nm11)rn1+ (2;0+2;1n+:::+2;m21nm21)rn2+:::+ (t;0+t;1n+:::+t;mt1nmt1)rntNonhomogenous recurrence relations Theorem 5:Ifa(p)nis a particular solution to the linear nonhomogeneous recurrence relation with constant coefficients,an=c1an1+c2an2+:::+ckank+F(n), then every solution is of the forma(p)n+a(h)nwherea(h)nis a solution of the associated homogeneous recurrence relation, a n=c1an1+c2an2+:::+ckank. 1

ICS 241: Discrete Mathematics II (Spring 2015)

Theorem 6:Assume thatansatisfies the linear nonhomogeneous recurrence relation with constant coefficients: a n=c1an1+c2an2+:::+ckank+F(n) withF(n)of the form:

F(n) = (btnt+bt1nt1+:::+b1n+b0)sn

whereb0;b1;:::;btandsare real numbers. Case 1:Ifsis not a characteristic root of the associated linear homogeneous recurrence relation with constant coefficients, there is a particular solution of the form (tnt+t1nt1+:::+1n+0)sn Case 2:Ifsis a characteristic root of multiplicitym, there is a particular solution of the form n m(tnt+t1nt1+:::+1n+0)sn

8.2 pg. 524 # 1

Determine which of these are linear homogeneous recurrence relations with constant coefficients.

Also, find the degree of those that are.

aan= 3an1+ 4an2+ 5an3

Yes. Degree 3.

ban= 2nan1+an2

No.2nis not a constant coefficient.

can=an1+an4

Yes. Degree 4.

dan=an1+ 2

No. This is nonhomogeneous because of the 2.

ean=a2n1+an2

No. This is not linear because ofa2n1.

fan=an2

Yes. Degree 2.

gan=an1+n

No. This is nonhomogeneous because of then.

2

ICS 241: Discrete Mathematics II (Spring 2015)

8.2 pg. 524 # 3

Solve these recurrence relations together with the initial conditions given. aan= 2an1forn1;a0= 3

Characteristic equation:r2 = 0

Characteristic root:r= 2

By using Theorem 3 withk= 1, we havean=2nfor some constant. To find, we can use the initial condition,a0= 3, to find it. 3 =20 3 =1 3 = So our solution to the recurrence relation isan= 32n. ban=an1forn1;a0= 2

Same as problem (a).

Characteristic equation:r1 = 0

Characteristic root:r= 1

Use Theorem 3 withk= 1like before,an=1nfor some constant. Find. 2 =10 2 = So the solution isan= 21n. But we can simplify this since1n= 1for anyn, so our solution isan= 2for anyn. can= 5an16an2forn2;a0= 1;a1= 0

Characteristic equation:r25r+ 6 = 0

Determinant:524(1)(6) = 2524 = 1

Since our determinant is greater than 0, we know we can use Theorem 1.

Find the characteristic root.

We can factorr25r+ 6 = 0into(r2)(r3) = 0.

So our roots arer1= 2andr2= 3.

Use Theorem 1 to find our general solution:an=12n+23nfor some constants1and 2.

Find1and2by using our initial conditions.

Fora0= 1

1 =120+230

1 =1+2

Fora1= 0

0 =121+231

0 = 21+ 32

Solve the system of equations:

1= 12 3

ICS 241: Discrete Mathematics II (Spring 2015)

0 = 2(12) + 32

0 = 222+ 32

0 = 2 +2

2=2

1= 1(2)

1= 3

Our solution isan= 32n23n

dan= 4an14an2forn2;a0= 6;a1= 8

Characteristic equation:r24r+ 4 = 0.

Determinant:164(1)(4) = 1616 = 0.

Determinant is 0, we can use Theorem 2.

Find the characteristic root.

Factorr24r+ 4 = 0to(r2)2= 0.

Our root isr= 2with multiplicity 2.

Use Theorem 2 to find our general solution:an=12n+2n2nfor some constants1and 2.

Find1and2by using our initial conditions.

Fora0= 6

6 =120+2020

6 =1

Fora1= 8

8 =121+2121

8 = 21+ 22

Solve the system of equations:

8 = 2(6) + 22

8 = 12 + 22

4 = 22

2=2

Our solution isan= 62n2n2n= (62n)2n.

ean=4an14an2forn2;a0= 0;a1= 1

Characteristic equation:r2+ 4r+ 4 = 0.

We can factorr2+ 4r+ 4 = 0into(r+ 2)2= 0

So our characteristic roots are -2 with multiplicity 2. Use Theorem 2:an=1(2)n+2n(2)nfor some constants1and2.

Find1and2

Fora0= 0

0 =1(2)0+20(2)0

1= 0

Fora1= 1

1 =1(2)1+21(2)1

1 =2122

4

ICS 241: Discrete Mathematics II (Spring 2015)

Solve the systems of equation and you get1= 0and2=1=2.

Our solution isan= (1=2)n(2)n=n(2)n1.

fan= 4an2forn2;a0= 0;a1= 4

Characteristic equation:r24 = 0.

Factor the equation and you get(r2)(r+ 2) = 0.

The characteristic roots arer1= 2andr2=2.

Use Theorem 1:an=12n+2(2)n.

By using initial conditions, you"ll get0 =1+2and4 = 2122. When solved,1= 1 and2=1

So the solution isan= 2n(2)n.

gan=an2=4forn2;a0= 1;a1= 0

Characteristic equation:r21=4 = 0.

Factor to get(r1=2)(r+ 1=2) = 0.

the characteristic roots arer1= 1=2andr2=1=2.

Use Theorem 1:an=1(1=2)n+2(1=2)n.

By using initial conditions, you"ll get1 =1+2and0 =1=22=2. When solved,

1= 1=2and2= 1=2.

So the solution isan= (1=2)(1=2)n+ (1=2)(1=2)n.

8.2 pg. 525 # 13

Find the solution toan= 7an2+ 6an3witha0= 9;a1= 10;a2= 32.

Characteristic equation:r37r6 = 0.

This is a 3rd degree equation, so we have to use Theorem 3 or 4.

Need to find roots. Use rational root test.

We know our possible roots are1;2;3;6.

Test to see which of these number will be our root for the equation.

Test1.

(1)37(1)6 =1 + 76 = 0Good! We know1is a root. Factor out(r(1))inr37r6 = 0to get(r+ 1)(r2r6) = 0. Continue factoring and we get(r+ 1)(r3)(r+ 2) = 0.

We know our characteristic roots:r1=1;r2= 3;r3=2.

Our general solution using Theorem 3 is:an=1(1)n+23n+3(2)n.

Find1;2;3by using the initial conditions.

Fora0= 9

9 =1(1)0+230+3(2)0

9 =1+2+3

Fora1= 10

10 =1(1)1+231+3(2)1

10 =1+ 3223

Fora2= 32

32 =1(1)2+232+3(2)2

5

ICS 241: Discrete Mathematics II (Spring 2015)

32 =1+ 92+ 43

Solve the system of equations:

9 =1+2+3

10 =1+ 3223

32 =1+ 92+ 43

Add the first equation and second equation together to get:

19 = 423

Add the second equation and third equation together to get:

42 = 122+ 23

Multiply19 = 423by 2 and add with41 = 122+ 23to get:

80 = 202

4 =2

Substitute2back in.

19 = 4(4)3

19 = 163

3 =3

With2and3, we can find1

9 =1+ 43

9 =1+ 1

8 =1

Our solution isan= 8(1)n+ 4(3)n+ (3)(2)n.

8.2 pg. 525 # 21

What is the general form of the solutions of a linear homogeneous recurrence relation if its char- acteristic equation has roots 1, 1, 1, 1, -2, -2, -2, 3, 3, -4? Use Theorem 4 with 4 roots that have multiple multiplicities. r

1= 1with multiplicity 4,r2=2with multiplicity 3,r3= 3with multiplicity 2, andr4=4

with multiplicity 1.

So our general solution is of the form:

a n= (1;0+1;1n+1;2n2+1;3n3)(1)n+(2;0+2;1n+2;2n2)(2)n+(3;0+3;1n)(3)n+ (4;0)(4)n

8.2 pg. 525 # 27

What is the general form of the particular solution guaranteed to exist by Theorem 6 of the linearquotesdbs_dbs11.pdfusesText_17
[PDF] la composante vivante dun milieu naturel

[PDF] les composantes de lenvironnement 6ème

[PDF] quelles sont les composantes de lenvironnement

[PDF] les composantes de l'environnement svt 6ème

[PDF] les composantes dun milieu naturel

[PDF] quelles sont les composantes dun milieu naturel

[PDF] les elements qui composent l'environnement

[PDF] les composantes de lenvironnement pdf

[PDF] 1.1.1 tenue des dossiers fournisseurs et sous-traitants

[PDF] 1.1.4 evaluation et suivi des stocks

[PDF] 1.2.3 traitement des devis des commandes

[PDF] 1.2.4 traitement des livraisons et de la facturation

[PDF] 1.3.1 suivi de la trésorerie et des relations avec les banques

[PDF] tenue des dossiers clients donneurs d ordre et usagers

[PDF] 2.2.3 suivi administratif des carrières