Suppose that I have coded a recursive function foo(i,j,k) and I would like to prove that it returns the correct value for all valid inputs i,j,k. (This is relevant to some dynamic programming algorithms)
To prove this with induction, I would like to represent this function's correctness with a proposition, such as:
$P(i, j, k)$ =
foo(i,j,k)returns the correct value for inputsi,j,k.
Can a proposition be dependent on 3 integers like this? If not, what is an alternative way of defining a similar proposition?
Thank you.
First, the proposition $P(i,j,k)$ clearly is dependent on all $3$ variables. And there is no issue with this. Indeed, in and of itself, this has nothing to do with induction.
But sure, let's suppose you want to prove $P(i,j,k)$ is true for any $i,j,k$ using induction. Well, there are several options here:
Sometimes it is possible to not involve all variables in the induction. So, for example, you could say: "Let's consider an arbitrary $i$ and $j$, but now prove that given this arbitrary $i$ and $j$, we can show that $P(i,j,k)$ is to for any $k$, by induction on $k$." So now you are doing induction on just one variable, but since $i$ and $j$ were arbitrary, you can generalize the result as desired.
Of course, sometimes you don't need induction at all. You just consider any arbitrary $i,j,k$, and prove $P(i,j,k)$ is true matter what.
You can also try and do inductions within inductions. For example, you could say: "Let's take an arbitrary $i$, but now prove that $P(i,j,k)$ is true for any $j$ and $k$ by induction on $j$. OK, so base case: let's show that for any $k$, we have $P(i,0,k)$. Now, maybe this is easy to show, and so no further induction on $k$ is needed. So, let's on tho the step case: Assume that for some arbitrary $j$, we have that for all $k$: $P(i,j,k)$ ... we now want to show that for all $k$: $P(i,j+1,k)$. Now maybe this latter result is not so easy to prove ... but maybe we can use induction on $k$ at this point. That is, first show that $P(i,j+1,0)$, and then show that for arbitrary $k$: $P(i,j+1,k)$ implies $P(i,j+1,k+1)$. So, in effect, you are doing an inductive proof as part of an inductive proof: doing an inductive proof on one variable inside an inductive proof on a different variable. But you are still doing them one at a time.
OK, so this is where I think you were going with your question: can you do induction on multiple variables at once? And the answer is yes! Now, this is not how induction is typically defined in your textbook, but it's really the same idea: suppose I show the following $4$ things:
A. $P(0,0,0)$
B. For any arbitrary $i$, $j$, and $k$: if $P(i,j,k)$, then $P(i+1,j,k)$
C. For any arbitrary $i$, $j$, and $k$: if $P(i,j,k)$, then $P(i,j+1,k)$
D. For any arbitrary $i$, $j$, and $k$: if $P(i,j,k)$, then $P(i,j,k+1)$
Do you see how if you have all these results, you have effectively proven that $P(i,j,k)$ is true for any $i,j,k$? Do you see how you effectively 'cover' or 'get to' all the possible $i,j,k$ triples? Or, in terms of the often-used analogy of falling domino stones, how every possible stone in this 3D array of domino stones falls over? Indeed, once you do this kind of visual, it is often not hard to set up some kind of induction that will do the job
OK, so which method should you be using? Well, you said that you are dealing with a recursive function. So, what you typically want to do, is to have your inductive proof follow that very recursive definition. For example, if the function recurses over $i$ and $k$, but not over $j$, then set up an induction over $i$ and $k$, but not $j$. If your recursive function recurses over multiple variables at once, then set up the induction on multiple variables at once accordingly. If the recursion subtracts $2$, then have your induction do the same thing ... and since that means that your function (in order to cover all possible triples) has multiple base cases, then your inductive proof should consider those very same base cases.