Determine whether each of these proposed definitions is a valid recursive defini

Question

Determine whether each of these proposed definitions is a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If f is well defined, find a formula for f) when n is a nonnegative integer and prove that your formula is valid. f(0) = 1, f(n) = -f(n - 1) for n > 1 f(0) = 1, f(t) = 0, f(2) = 2, f(n) = 2f(n - 3) for n > 3 f(0) = 0, f(1) = 1, f(n) = 2f(n + 1) for n > 2 f(0) = 0, f(1) = 1, f(n) = 2f(n - 1) for n > 1 f(0) = 2, f(n) = f(n - 1) if n is odd and n > 1 and f(n) = 2 f(n - 2) if n > 2

Explanation / Answer

b)

Recurrence is valid since nth term depends on (n-3)th term.

First three terms are defined so third term can be computed using 0th term, 4th term using 1st term, 5th term using 2nd term

6th term using third term and so on. So recurrence is well defined and for all n natural numbers f(n) can be computed.

f(3)=2f(0)=2

f(4)=2f(1)=0

f(5)=2f(2)=2^2

f(6)=2f(3)=2^2

f(7)=2f(4)=0

f(8)=2f(5)=2^3

....

f(3n)=2^n

f(3n+1)=0

f(3n+2)=2^(n+1)

Check if formula is valid

f(0)=2^0=1

f(1)=0

f(2)=f(3*0+1)=2^1=2

f(3n)=2^n=2*2^(n-1)=2f(3n-3)

f(3n+1)=0=f(3(n-1)+1)=f(3n+1-3)

f(3n+2)=2^(n+1)=2*2^n=2f(3(n-1)+2)=2f(3n+2-3)

Hence the formula is valid.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.