Mathematical induction hw

CSC321 Fall 2017

Homework #1

1. Prove by induction : 1

( !) ( 1)! 1 n

i

i i n 

   [ch 2.2 p.38 #3]

2. Prove that ! ( ) n

n O n . [ch 2.3 p.53 +21]

3. Prove that 2 ( !) n

O n . [ch 2.3 p.53 #22]

4. Use mathematical induction to show that 1

2 1 n

n f n

    where

. n

f is the nth Fibonacci number

5. For the following, what is the complexity of the given code segments:

[the number of times the statement x = x + 1 is executed.]

a)

for i = 1 to n for j = 1 to i for k = 1 to j x = x + 1

b)

for i = 1 to n for j = 1 to i for k = 1 to i x = x + 1

c)

i = n While (i ≥ 1 ){ x = x + 1 i = i/2 }