Discrete Mathematics

SKKU Math Lectures and Labs

Prof : Sang-Gu LEE  (http://matrix.skku.ac.kr/sglee/ )

http://matrix.skku.ac.kr/2018-DM/DM-Labs.htm  Discrete Math Labs (실습실)

http://matrix.skku.ac.kr/2018-DM-PBL/      (PBL report 보고서)
http://matrix.skku.ac.kr/2018-DM-PBL-Eng/  (PBL report Eng, 영문 보고서)

Chapter 7  Recurrence Relations

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-7/

DM Ch. 7, 동영상강의 https://youtu.be/1n0dC_ICo4U

Ch 7 & Ch 8 Preview QnA https://youtu.be/r0M7OuRhqnc

Problem 1

[Final OK by TA] Ch. 7 P.424 Problem 1 solved by 전솔람 Finalized by 칭키즈, 김영철 , Muhammad

Problem

Answer part (a)-(c) for the sequence defined by rules:

1. The first term is 3.

2. The n th term is n plus the previous term.

(a) Write the first four terms of the sequence.

(b) Find an initial condition for the sequence.

(c) Find a recurrence relation for the sequence.

Solution

1.    Let n-th term of the sequence be anwhich logically makes the previous term an-1.

2.     Hence, the formula of n-th term is  an = n + an-1​​

3.     Let me remind you that the first term is 3 ( a1=3 )

4.     Hence to find another three elements:

n =
2     ->   a2 = 2 + a2-1 = 2 + a= 2 + 3 = 5
n =
3     ->   a3 = 3 + a3-1 = 3 + a2 = 3 + 5 = 8
n =
4     ->   a4 = 4 + a4-1 = 4 + a= 4 + 8 = 12

(a) Write the first for terms of the sequence.

a1 = 3,  a2 = 5,  a3 = 8 ,  a= 12

(b) Find an initial condition for the sequence.

a= 3

(c) Find a recurrence relation for the sequence.

an = n + an-1

Comment:

일정한 규칙의 조건을 가지고 단계별로 점화식으로 표현하는 방법에 대해 배우게 되었다.

Problem 2

[Final OK by TA] Ch. 7 P.424 Problem 2 Solved by 전솔람 finilized by 칭기즈 , 김영철, Muhammad

Problem

Assume that a person invest 4000 dollars at 17 percent interest compounded annually. Let A(n) represent the amount at the end of n years. Find a recurrence relation and an initial condition for the sequence A(0), A(1), ......

 Definition  1.1 Solution

1.    Let a0 be the initial amount invested
-->  a
0=4000

2.    After 1 year, a1 will be
-->  a
1 = a+ 0.17 a= 1.17 a0

3.    After 2 years, a2 will be
-->  a
2 = a+ 0.17 a​​1.17 a1 = (1.17)a0

4.    Thus, after n years, an will be
-->  a
n = an-1 + 0.17 an-1 = (1.17) an-1 = ... = (1.17)a0

Initial state:  a0=4000
Recurrence relation:   an = (1.17)an-1 , where a0=4000

Comment:

복리계산에 대한 내용과 그것을 점화식으로 표현해 볼 수 있었다.

Problem 3

[Final OK by TA] Ch. 7 P.424 Problem 3 solved by 서명원 Finalized by 김영철, Muhammad, 전종문

Problem Solution

1.    Let X be an n-element set and choose x X and k be a fixed integer (0 ≤ k ≤ n - 1)

2.     We can select a k-element subset Y  from X - {x} in C(n-1, k) ways.

3.     Next, we can partition Y in Pk ways.

4.     This partition (from step 3) along with the set X - Y  -> partitions X.

5.      Since this works for every partition of X, the recurrence relationship is proven

Another Solution

To prove Pn satisfies the recurrence relation, we can find a relationship between Pn and Pn-1.

Pn   n-1n=0   C(n-1,k)  Pk = ( n-2n=0   C(n-2,k)  Pk )*n-1 +C(n-1,n-1)Pn-1

= (Pn-1) *n-1 + Pn-1​​= n*Pn-1​​​

Then we showed that Pn = n *Pn-1​​​​ satisfies the recurrence relation

Comment:

일정한 규칙이 반복되는 구조일 때, 점화식으로 표현할 수 있다는 것을 알 수 있었다.

Problem 4

[Final OK by TA]Ch 7, P424, P.4 Solved by 서명원, Finalized by Muhammad

Problem Solution

If the first domino is placed as shown,

there are n-1 ways to cover the 2 x (n-1) board that remains. If the first two dominoes are placed as shown,

there are n-2 ways to cover the 2 x (n-2) board that remains. If follows that an = a n-1 + a n-2.

By inspection, a1 = 1 and a2 = 2.

Since (an} satisfies the same recurrence relation as the Fibonacci sequence

a1 = f2 and a2 = f an = f n+1 ,where { f n } is the Fibonacci sequence.

Comment:

그림을 통해 점화식의 규칙을 알 수 있었고 피보나치 수열의 점화식에 대해서도 알 수 있었다.

Problem 5

[Final OK by SGLee] Ch 7, P424, P.5 칭기즈 finalized by 오동찬

Problem

Is the recurrence relation

an = an-1 + an-3

a linear homogeneous recurrence relation with constant coefficients?

Solution

 Definition  2.6 Thus, the recurrence relation in the definition is linear because the right-hand side is a sum of previous terms of the sequence which are

an-1 and  an-3​​

Notice that:

an = 1 *an-1 + 1*an-3

Hence, 1   is a constant coefficient.​​

The recurrence relation,

an=an-1+an-3

is linear homogeneous recurrence relation with constant coefficients  with

c1 = 1, c2 = 0, c3 = 1, c4 = c5 = … = 0

Comment:

이 문제를 통해 homogeneous recurrence relation의 정의를 확인해 볼 수 있었다.

Problem 6

[Final OK by SGLee] Ch. 7 P.424 Problem 6 전솔람, 김희성, 칭기즈 by Muhammad

Problem

Solve the recurrence relation subject to the initial conditions.

6. an = - 4 an-1 - 4 an-2 a= 2 , a1 = 4

Solution

By using the quadratic formula derived from theorem 2.14 we can see that we can form a second power polynomial by replacing (an = x2an-1 = x, an-2 =1) as following:

x2 = -4x-4

x2+4x+4 = 0

D = b2-4*a*c = 16-16 = 0

x1  and x2 = -4/2 = -2

There is only one root 2 with multiplicity 2.  So,

an=a*(-2n)+b*n(-2n)

* Our next step is to find the coefficients (a, b) using:

a= 2

a1 = 4

1.For n=0 : a0=a*(-20)+b*0(-20)=2

a =2

2.For n=1 : a1=2*(-21)+b*1(-21)=4 =-4-2b =4-2b =8

b=-4

Thus,   an=2*(-2n)-4*n(-2n)

an=2(-2n) - 4n(-2n)

Comment:

Second-order linear homogeneous recurrence relation with constant coefficients일 때 점화식을 푸는 방법에 대해 알 수 있었다.

Problem 7

[Final OK by TA] Ch. 7 P.424 Problem 7 solved by 전솔람 Finalized by 김희성, 칭키즈, Muhammad

Problem

Solve the recurrence relation subject to the initial conditions.

7. an = 3an-1 + 10an-2 ,  a(0) = 4  a(1) = 13

Solution

By using the quadratic formula derived from theorem 2.14 we can see that we can forma second power polynomial by replacing(an = x2an-1 = x, an-2 =1) as following:

x2=3x+10

x2-3x-10=0

(x-5)(x+2)=0

X=5   x=-2

There are 2 roots so

an=a*(5n)+b*(-2n)

* Our next step is to find the coefficients(a,b) using:

a0=4

a1=13

*For n=0 : a0=a*(50)+b*(-20)=2 =a+b=4

*For n=1: a1=2*(51)+b*(-21)=13 =5a-2b=13

*Next: we will solve these equations for (a,b):

a+b=4 (1)

5a-2b=13 (2)

Let’s multiply equation (1) by 2: 2a+2b=8 (3)

Let’s add equation (3) and (2): a=3

Hence, 3+b=4  b=1

Thus,

an=3*(5n)+1*(-2n)

an=3*(5n)+1*(-2n)

Comment:

Second-order linear homogeneous recurrence relation with constant coefficients일 때 점화식을 푸는 방법에 대해 알 수 있었다.

Problem 8

[ReFinalized] Ch.7, P.424, Problem7, 칭기즈, Muhammad,김희성

Problem

Let Cn denote the number of strings over {0,1,2} of length n that contain an even number of 1's.Write a recurrence relation and initial condition that define the sequence C1,C2 , ...

Solve the recurrence relation to obtain an explicit formula for Cn. Solution

Cn=(a)+(b)+(c) , where a,b,c are string types formed by {0,1,2}

there are 3 ways to form a n-length string with even number of 1's:

(a) An n-length string begins with 0 and contain an even number of 1's.

Since any (n-1)-length string containing even number of 1's  can follow the initial 0

Cn-1

(b) An n-lengths string begins with 2 and contain an even number of 1's.

Since any (n-1)-length string  containing even number of 1's  can follow the initial 2, Cn-1

(c) As n- length string that begins with 1 and (n-1)-length string should contain odd number of 1's

(n-1)-length string should contain odd number of 1's 3n-1​​Cn-1

Thus,

Cn= Cn-1​​+Cn-1​​+3n-1​​-Cn-1 = 3n-1​​+Cn-1

Initial condition : C1=2

Cn =  3n-1​​+Cn-1​​ = 31​​​+32​​+33  +... + 3n-1​​+ C1 =2+(3n-3)/(3-1) =(3n+1)/2

A recurrence relation and initial condition : Cn = 3n-1​​ + Cn-1

Initial condition : C1=2

Solution :  Cn (3n+1)/2

Comment:

The idea of this questions is not simple . So I recommend you to go through the different theorems/principles mentioned through the solution before.

점화식의 규칙이 잘 안 보일 때, 경우를 나누어서 생각하면 된다는 것을 알 수 있다.

Problem 9

[Final OK by SGLee] Ch 7, P424, P.9, by 칭기즈, 전종문 (Read This comment)

Problem

This algorithm evaluates the polynomial at the point t.

Input: The sequence of coefficients c0,c1, ... ,cn, the value t, and n

Output: p(t)

poly(c,n,t){

f(n==0)                        line 1

return c0                   line 2

return t*poly(c,n-1,t)+cn       line 3

}

Let bn be the number of multiplications required to compute p(t).
Find the recurrence relation and an initial condition for the sequence {bn}.

Solution

Let  bn the total number of multiplications at line 3 required to compute p(t).

Initial condition :   b= 0    (The total number of multiplications = 0 when n=0 )

At  line 1-2  the number of multiplications is 0.

At the  line 3,  there is 1 multiplication and

in this line the function is invoked by itself with the input of size n-1, hence there is bn-1 number of multiplications at this line.

The total number of multiplications :    bn = bn-1 + 1

The recurrence relation and an initial condition for the sequence {bn} is

bn = bn-1 + 1  with  b0=0

Comment:

At the recurrence function part in the given code, the line 3 [return t*poly(c, n-1,t)+cn ] has a very similar format of recurrence relations that we are looking for.

재귀함수의 반환부분이 점화식의 꼴과 비슷하다는 점을 알게 되었다.

Problem 10

[Final OK by SGLee] Ch 7, P424, P.10 solved by 칭기즈 Finalized by 김영철

Problem Solution

0.    In problem 9 we derived a recurrence relation and initial condition as below :
bn=bn-1+1
b0=0​​

​​1.    Thus,
For n=1 :
b
1= b1-1+1=b0+1=0+1=1
For n=2 :
b
2= b2-1+1=b1+1=1+1=2
For n=3:
b3= b3-1+1=b2+1=2+1=3

2.     So we can find out that
b1=1
b
2=2
b
3=3

b1=1 , b2=2 ,  b3=3

Comment:

초항을 점화식에 대입하여 차례대로 점화식의 다음 항을 구하는 문제이다.

Problem 11

[Final OK by SGLee] Ch 7, P424, P.11 solved by 칭기즈 Finalized by 김영철

Problem Solution

0. In Exercise problem 9, we derived a recurrence relation and initial condition.
--> b
n = bn-1 + 1
--> b
= 0​​

1.  [Solve]   Thus, Let's solve by iteration :
--> b
n  = bn-1 + 1
= b
n-2 + 1 + 1
= b
n-3 + 1 + 1 + 1

2.   If we keep substitute like that, we will get
-->  b
n  ... = b+ 1 + 1 + 1 + ... + 1
= 0 + n*1
= n
So we get   b
= n

b= n                      ​​

Comment:

점화식의 푸는 두 가지 방법 중에서 iteration의 방법으로 점화식을 풀었다.

Problem 12

[Final OK by TA] Ch 7, P.424, Problem.12 Finalized by 전종문

Problem

Suppose that we compute P(t)  by a straightforward technique that requires n - k multiplications to compute ckt n-kHow many multiplications would be required to compute P(t) ?

Would you prefer this method or the preceding algorithm? Explain.

Solution

We already know the equation of bn which from solution of problem 11.

bn = n

Derived from this relationship, total P(t)  is 1 + 2 + 3 + 4 + ... + n and it is (n2+n)/2.

and also is big O (that have n2 parameter) O( n2).

(n2+n)/2  = O( n2, given algorithm(O( n) system is much faster than the straight forward method(O( n2). so, preferred

Comment:

we can see that big O notation can be used to show the complexity of time of code

두 방법의 효율성을 비교할 때, notation으로 비교하여 어느 방법이 더 선호되는지를 알 수 있는 문제였다.

Computer Exercise 1

[Final OK by SGLee] Ch 7, P424, Com Exs.1, by 김정주, 김희성, 전종문

Problem

1. Write a program that prints the amount accumulated yearly if a person invests n dollars at p percent compounded annually.

Solution

Python code :

dollar=float(input("dollar: "))

interest=float(input("rate: "))

year=float(input("year: "))

def compound(dollar,interest,year):

if year<=0:

return dollar

else:

return compound(dollar,interest,year-1)*(1+interest/100)

print(compound(dollar,interest,year), "dollars accumulated")

result :

C code:

​​#include

int main()

{

int dollar, rate, year;

double amount;

printf("In put dollar : ");

scanf_s("%d",&dollar);

printf("In put rate : ");

scanf_s("%d", &rate);

printf("In put year : ");

scanf_s("%d", &year);

amount = dollar;

for (int i = 1; i <= year; i++) {

amount = amount + amount*((double)rate / 100);

}

printf("amount : %f", amount);

return 0;

} This is sage code:     (Practice in http://sage.skku.edu/  or  https://sagecell.sagemath.org/)

# Computing Compound Interest

@interact

def _(n=input_box(default=10, label='num of yrs'), A=input_box(default=100, label='init. amount'),r=input_box(default=0.05, label='interest rate')):

compound_interest = A

if n == 0:

print "compound interest = ", compound_interest

return

for i in range(n):

compound_interest = (1.0 + r)*compound_interest

print "compound interest = ", compound_interest

return Comment:

코드를 통해 이 재귀함수의 점화식이 An=An-1*(1+interest rate)n=year, A0=init amount 임을 알 수 있다.

Computer Exercise 3

[Final OK by SGLee] Ch 7, P424, Com Exs.3, by 김정주, 전종문

Problem

Write a program that solves the three-peg Tower of Hanoi puzzle.

Solution

Python code:

count=0

def hanoi(A,B,C,n):

global count

if n==1:

print("Move ring "+str(n)+" from "+A+" to "+C)

count+=1

else:

hanoi(A,C,B,n-1)

print("Move ring "+str(n)+" from "+A+" to "+C)

count+=1

hanoi(B,A,C,n-1)

n=int(input("Enter the n : "))

hanoi('A','B','C',n)

print("total moves :",end='')

print(count)

Result: Comment:

Hanoi 라는 함수 안에 Hanoi 함수를 넣음으로써 복잡한  three-peg Tower of Hanoi puzzle 에서 Ring 을 옮기는 순서를 기존보다 매우 간단하게 표현 할 수 있게 되었다.