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 \geq 1

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

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

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

 

Solution

 a) f(n) = 5\left \lceil \frac{n}{2} \right \rceil. We prove by induction on n. This is true for n = 0 and n = 1 since f(0) = = 5\left \lceil \frac{0}{2} \right \rceil  = 5^{0} = 1 and f(1) = = 5\left \lceil \frac{1}{2} \right \rceil  = 5^{1}= 5. If it is true for n =k with k\geq1 , then we have f(k +1) = 5f(k +1) = 5\left \lceil \frac{k + 1}{2} \right \rceil 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 \geq1 , then we have f(k + 1) = f(k) – 1 = 7 – (k + 1) as desired.

 

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

 

Leave a Reply