Let function f: Z nonneg x Z nonneg to Z nonneg f(0,y)=1 for all y >=0 f(1,0)=2

Question

Let function f: Z nonneg x Z nonneg to Z nonneg f(0,y)=1 for all y >=0 f(1,0)=2 f(x,0)=x+2, x>=2 f(x+1, y+1)=f(f(x,y+1),y) 1. Find a formula (closed form) in terms of x to describe f(x,1), x>=1 2. Find a formula (closed form) in terms of x to describe f(x,2), x>=0 Let function f: Z nonneg x Z nonneg to Z nonneg f(0,y)=1 for all y >=0 f(1,0)=2 f(x,0)=x+2, x>=2 f(x+1, y+1)=f(f(x,y+1),y) 1. Find a formula (closed form) in terms of x to describe f(x,1), x>=1 2. Find a formula (closed form) in terms of x to describe f(x,2), x>=0 f(0,y)=1 for all y >=0 f(1,0)=2 f(x,0)=x+2, x>=2 f(x+1, y+1)=f(f(x,y+1),y) 1. Find a formula (closed form) in terms of x to describe f(x,1), x>=1 2. Find a formula (closed form) in terms of x to describe f(x,2), x>=0

Explanation / Answer

1.

Case 1:x=1

f(1,1)=f(f(0,1),0)=f(1,0)=2

Case 2:x>1

f(x,1)=f(f(x-1,1),0)=f(x-1,1)+2=f(x-2,1)+2*2=f(x-k,1)+2*k

We can do this till x-k=1

k=x-1

So,f(x,1)=f(1,1)+2*(x-1)=2+2*(x-1)=2x

2.

f(x,2)=f(f(x-1,2),1)=2*f(x-1,2)....=2^kf(x-k,2)

Again as before k=x-1 so we have

f(x,2)=2^{x-1}f(1,2)

f(1,2)=f(f(0,2),1)=f(1,1)=f(f(0,1),0)=f(1,0)=2

Hence, f(x,2)=2^x

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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