# Thread: Complicated induction proof, where you are given a function of two variables

1. ## Complicated induction proof, where you are given a function of two variables

Let N denote the natural numbers. Let f: NxN -> N be defined by
f(a,0) = a for all natural numbers a
f(0,b) = 2b for all natural number b
f(a,b) = [f(a-1, b) + f(a, b-1)+3]/2 for all positive integers a,b

Compute f(a,b) for all 0 <= a,b <= 3
Prove that f(a,b)<= 2(a+b) for all natural numbers a,b by induction

Any guidance and help is much appreciated I am not sure where to begin with this problem. Thank you.

2. ## Re: Complicated induction proof, where you are given a function of two variables

Originally Posted by ak12
Let N denote the natural numbers. Let f: NxN -> N be defined by
f(a,0) = a for all natural numbers a
f(0,b) = 2b for all natural number b
f(a,b) = [f(a-1, b) + f(a, b-1)+3]/2 for all positive integers a,b

Compute f(a,b) for all 0 <= a,b <= 3
Prove that f(a,b)<= 2(a+b) for all natural numbers a,b by induction

Any guidance and help is much appreciated I am not sure where to begin with this problem. Thank you.
If $f$ is defined on $N \times N$ then $f(a,0)$ and $f(0,b)$ aren't defined so the problem makes no sense.

3. ## Re: Complicated induction proof, where you are given a function of two variables

I highly doubt my professor would give us a problem that isnt possible (i hope) I am attaching a screen shot of the question please let me know if it still doesnt make sense.

4. ## Re: Complicated induction proof, where you are given a function of two variables

Normally "N" is the set of positive integers so doesn't include 0. Just use the non-negative integers so that 0 is included. You need to do a "double induction". First prove that, for n a non-negative integer, $\displaystyle f(m, 0)\ge m$, then that $\displaystyle f(0, n)= n$. Then continue the indutions on a and b.