Question-74

Question-74

Determine whether each of these proposed definitions is a valid recursive definitions of a function f from the set of nonnegative to the set of integers. If f is well defined, find a formula for f(n) when n is a nonnegative integer and prove that your formula is valid.

 a)     f(0) = 1 , f(n) = 5f(n – 2) for n 1

b)    f(0) = 2, f(n) = f(n – 1) – for n 1

c)     f(0) = 3, f(1) = 6, f(n) = f(n – 1) – 1 for n 2

d)    f(0) = 1, f(1) = 4, f(n) = 4 f(n – 1) if n is odd and n 1 and f(n) = 16 f(n – 2) if n is even and n 2

 

Solution

 a) f(n) = 5. We prove by induction on n. This is true for n = 0 and n = 1 since f(0) = = 5 = 1 and f(1) = = 5= 5. If it is true for n =k with k1 , then we have f(k +1) = 5f(k +1) = 5 as desired.

 

b) f(n) = 2 – n. We prove this by induction on n .  This is true for n = 0 since 2 – 0 = 2 . If it is true for n = k , then we have f(k + 1) = f(k) – 1 = 2 –  (k + 1)  as desired.

 

c) f(n) = 7 – n .  We prove this by induction on n . This is true for n = 0 and n = 1 since f(0) = 7 – 0 = 7 and f(1) = 7 – 1 = 6 . If it is true fir n = k with k 1 , then we have f(k + 1) = f(k) – 1 = 7 – (k + 1) as desired.

 

d) f(n) = . We prove this by induction on n . This is true for n = 0 and n = 1 since f(0) = = 1 and f(1) = = 4. If it is true for n = k with k odd, then f(k) = 4 f(k – 1) = . For even k > 1 we have f(k) = 16 f(k – 2) = .