[PDF] 3. Recurrence 3.1. Recursive Definitions. To construct a recursively





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.

3. RECURRENCE 120

3. Recurrence

3.1. Recursive Denitions.To construct arecursively dened function:

1. Initial Condition(s) (or basis): Prescribe initial value(s) of the function.

2. Recursion: Use a xed procedure (rule) to compute the value of the function at

the integern+ 1 using one or more values of the function for integersn.

To construct arecursively dened set:

1. Initial Condition(s) (or basis): Prescribe one or more elements of the set.

2. Recursion: Give a rule for generating elements of the set in terms of previously

prescribed elements.

Discussion

In computer programming evaluating a function or executing a procedure is often accomplished by using arecursion. A recursive process is one in which one or more initial stages of the process are specied, and thenth stage of the process is dened in terms of previous stages, using some xed procedure. In a computer program this is usually accomplished by using a subroutine, such as a \For" loop, in which the same procedure is repeated a specied number of times; that is, the procedurecalls itself. Example3.1.1.The functionf(n) = 2n, wherenis a natural number, can be dened recursively as follows:

1. Initial Condition:f(0) = 1,

2. Recursion:f(n+ 1) = 2f(n), forn0.

For any particularn, this procedure could be programmed by rst initializingF= 1, and then executing a loop \Fori= 1ton,2F=F." Here is how the denition gives us the rst few powers of 2: 2

1= 20+1= 202 = 2

2

2= 21+1= 212 = 22 = 4

2

3= 22+1= 222 = 42 = 8

3. RECURRENCE 121

3.2. Recursive Denition of the Functionf(n) =n!.

Example3.2.1.The factorial functionf(n) =n!is dened recursively as follows:

1. Initial Condition:f(0) = 1

2. Recursion:f(n+ 1) = (n+ 1)f(n)

Discussion

Starting with the initial condition,f(0) = 1, the recurrence relation,f(n+ 1) = (n+ 1)f(n), tells us how to build new values offfrom old values. For example,

1! =f(1) = 1f(0) = 1,

2! =f(2) = 2f(1) = 2,

3! =f(3) = 3f(2) = 6, etc.

When a functionf(n), such as the ones in the previous examples, is dened recursively, the equation givingf(n+ 1) in terms of previous values offis called a recurrence relation.

3.3. Recursive Denition of the Natural Numbers.

Definition3.3.1.The set of natural numbers may be dened recursively as fol- lows.

1. Initial Condition:02N

2. Recursion: Ifn2N, thenn+ 12N.

Discussion

There are a number of ways of dening the setNof natural numbers recursively. The simplest denition is given above. Here is another recursive denition forN. Example3.3.1.Suppose the setSis dened recursively as follows:

1. Initial Condition:0;12S,

2. Recursion: Ifx;y2S, thenx+y2S.

3. RECURRENCE 122

ThenS=N.

Notice that, in the recursive step,xandydon't have to represent dierent num- bers. Thus, havingx=y= 12S, we get1+1 = 22S. Then we get1+2 = 32S.

And so on.

It should be noted that there is anextremal clausein recursively dened sets. If you cannot build a given element in a nite number of applications of the recursion then it is not in the set built from the recursive denition. To prove an element is in a recursively dened set, you must show that element can be built in a nite number of steps. Example3.3.2.Prove that the setSrecursively in Example 3.3.1 is equal to the setNof natural numbers. Proof.We will show thatS=Nby showing separately thatSNandNS.

1. First we showNS. Prove by induction thatn2Sfor every natural number

n0. (a) Basis Step. 0;12Sby denition. (b) Induction Step. Supposen2S, for somen1. Then, by the recursion step, n2Sand 12Simplyn+ 12S. Thus, by the rst principle of mathematical induction,n2Sfor every natural numbern0.

2. Now we showSN. This time we apply the second principle of mathematical

induction onnto show that ifs2Sis produced by applyingnsteps (1 initial condition andn1 recursive steps), thens2N. (a) Basis Step. After one step the only elements produced are 0 and 1, each of which is inN. (b) Induction Step. Supposen1 and assume any element inSproduced by applyingnor fewer steps is also an element ofN. Supposes2Sis produced by applyingn+1 steps. Sincen+12, there must be two elementsxandy inS, such thats=x+y. Bothxandymust have been produced by applying fewerthann+1 steps, sincesis produced by applyingn+1 steps, and we use one step to obtainsfromxandy. By the induction hypothesis bothxandy are elements ofN. Since the sum of two natural numbers is again a natural number we haves2N.

3.4. Proving Assertions About Recursively Dened Objects.Assertions

about recursively dened objects are usually proved by mathematical induction. Here are three useful versions of induction. In particular, note the third version which we introduce here.

3. RECURRENCE 123

Version 1.Second Principle of Induction

a. Basis Step: Prove the assertion for the initial conditions. (The assertion may have to be veried for more than one particular value.) b. Induction Step: Assume the assertion is true for integersn, and use the recurrence relation to prove the assertion for the integern+ 1. Version 2. a. Basis Step: Prove the assertion for the initial conditions. (The assertion may have to be veried for more than one particular value.) b. Induction Step: Assume the assertion is true when the recursive de- nition has been applied less than or equal to n times for some integer n0, and use the recurrence relation to prove the assertion when the recursive denition is appliedn+ 1 times. Version 3.Generalized or Structural Principle of Induction: Use to prove an assertion about a setSdened recursively by using a setXgiven in the basis and a set of rules usings1;s2;:::;sk2Sfor producing new members in the recursive set. a. Basis Step: Prove the assertion for everys2X. b. Induction Step: Lets1;s2;:::;sk2Sbe arbitrary and assume the assertion for these elements (this is the induction hypothesis). Prove all elements ofSproduced using the recursive denition ands1;s2;:::;sk satises the assertion.

Discussion

Example3.4.1.LetS, a subset ofNN, be dened recursively by

1. Initial Condition:(0;0)2S

2. Recursion: If(m;n)2S, then(m+ 2;n+ 3)2S.

Prove that if(m;n)2S, thenm+nis a multiple of 5.

Proof.We use the Generalized Principle of Induction.

1. Basis Step: Show the statement for (0;0): 0 + 0 is a multiple of 5. Since 0 = 05

this is clear.

2. Inductive Step: Let (m;n)2Sand assumem+nis a multiple of 5. Show the

statement is true for (m+ 2;n+ 3). In other words, show (m+ 2) + (n+ 3) is a multiple of 5. (m+ 2) + (n+ 3) = (m+n) + 5 We knowm+nis a multiple of 5 and clearly 5 is a multiple of 5, so the sum must also be a multiple of 5. This proves the induction step.

3. RECURRENCE 124

Therefore, by the rst principle of mathematical induction if (m;n)2S, thenm+n is a multiple of 5. Exercise3.4.1.Suppose the setSis dened recursively as follows:

1.12S,

2. Ifx2S, then2x2S.

Prove thatS=f2njn0g.

Exercise3.4.2.Suppose the setSis dened recursively as follows:

1.0;12S,

2. Ifx;y2S, thenxy2S.

What are the elements ofS? Prove that your answer is correct.

Example3.4.2.Supposef:N!Ris dene recursively by

1. Initial Condition:f(0) = 0

2. Recursion:f(n+ 1) =f(n) + (n+ 1), forn0.

Thenf(n) =n(n+ 1)2

for alln0 Proof.1. Basis Step (n= 0):f(0) = 0, by denition. On the other hand

0(0 + 1)2

= 0. Thus,f(0) =0(0 + 1)2

2. Inductive Step: Supposef(n) =n(n+ 1)2

for somen0. We must prove f(n+ 1) =(n+ 1)((n+ 1) + 1)2 f(n+ 1) =f(n) + (n+ 1) (recurrence relation) n(n+ 1)2 + (n+ 1) (by the induction hypothesis) = (n+ 1)n2 + 1 = (n+ 1)n+ 22 (n+ 1)((n+ 1) + 1)2

3. RECURRENCE 125

Therefore, by the rst principle of mathematical inductionf(n) =n(n+ 1)2 for alln0. Exercise3.4.3.Supposef:N!Ris dene recursively as follows:

1.f(0) = 0,

2.f(n+ 1) =f(n) + (2n+ 1), forn0.

Prove thatf(n) =n2for alln0.

3.5. Denition offn.

Definition3.5.1.Letf:A!Abe a function. Then we denefnrecursively as follows

1. Initial Condition:f1=f

2. Recursion:fn+1=ffn, forn1.

Discussion

Example3.5.1.Prove that iffis injective, thenfnis injective forn1.

Proof.Assumefis injective.

1. Basis Step:f1=fis injective by our assumption.

2. Inductive Step: Letn1 and assumefnis injective. Provefn+1is injective.

Recall that to provefn+1is injective we must show8a;b2A[(fn+1(a) = f n+1(b))!(a=b)]

Assumea;b2Aandfn+1(a) =fn+1(b).

f n+1(a) =fn+1(b) (recurrence relation) (ffn)(a) = (ffn)(b) (recurrence relation) f(fn(a)) =f(fn(b)) (by the denition of composition) f n(a) =fn(b) (since f is injective) a=b(by the induction hypothesis,fnis injective) Therefore, by the rst principle of mathematical inductionfnis injective for all positive integers.

3. RECURRENCE 126

Exercise3.5.1.Prove that iffis surjective thatfnis surjective.

3.6. Example 3.6.1.

Example3.6.1.Given a real numbera6= 0, deneanfor all natural numbers,n, inductively by

1. Initial Condition:a0= 1

2. Recursion:a(n+1)=ana

Theorem3.6.1.8m8n[aman=am+n]wherem;nare natural numbers. Proof.Proof that (8m)(8n)[aman=am+n], wherem;nare natural numbers. We accomplish this by assumingmis an arbitrary natural number and proving8n[aman= a m+n] by induction onn.

1. Basis Step (n= 0): Showama0=am+0.

This follows directly from the initial condition of the denition:a0= 1, there- foreama0=am(1) =am=am+0.

2. Induction Step:

Induction hypothesis: Letnbe a natural number and assumeaman=an+m.

Proveaman+1=am+(n+1).

a man+1=amanaby the recursive part of the denition:an+1=ana =am+naby the induction hypothesis =a(m+n)+1=a(m+(n+1))by the recursive part of the denition

By induction,8n[aman=am+n].

Sincemwas an arbitrary natural number the statement is true for all natural numbers m.

Discussion

Here we see a recursive denition for the functionf(n) =an, wherenis a natural number andais an arbitrary nonzero real number followed by a proof of one of the laws of exponents,am+n=aman. This proof uses both mathematical induction and Universal Generalization. We xmas some arbitrary natural number and then proceed to use induction onn. We do not need to use induction on bothmandn simultaneously. When there are two dierent variables, this is a standard strategy to try. There are circumstances, however, when this strategy doesn't work so that you

3. RECURRENCE 127

would need to use induction onbothof the variables (double induction). We will not encounter these kinds of problems in this course, however.

3.7. Fibonacci Sequence.

Definition3.7.1.The Fibonacci sequence may be dened recursively as follows:

1. Initial Conditions:F(0) = 0;F(1) = 1

2. Recursion:F(n+ 1) =F(n) +F(n1)forn1

Discussion

The famousFibonacci sequenceis dened here using a recursively dened function. The denition of the Fibonacci sequence requires two initial conditions. There are no limits on the number of initial conditions on a recursively dened object { only that there be a xed nite number in each instance. Example3.7.1.SupposeF(n),n0, denotes the Fibonacci sequence. Prove that11< R(n)<2 for alln3.

1. Basis Step (n= 3):R(3) =F(4)F(3)=32

, and 1<32 <2.

3. RECURRENCE 128

2. Induction Step: Suppose 1< R(n)<2 for somen3. We need to prove

1< R(n+ 1)<2.

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

F(n+ 1) +F(n)F(n+ 1)by the recursive denition ofF(n) = 1 +

F(n)F(n+ 1)or

R(n+ 1) = 1 +1R(n)

By the inductive hypothesis 1< R(n)<2; and so

1>1R(n)>12

Thus,

2>1 +1R(n)>32

>1; or

1<1 +1R(n)<2:

Substituting from above, we have

1< R(n+ 1)<2:

By the rst principle of mathematical induction, 1