Induction principle on two variables proof-assuming upto $P(k,l) $ the statement is true.

47 Views Asked by At

In induction principle let a statement $P (x,y) $ needed to be proven. $P (1,1) $ is true. If we assume that upto $P (k,l) $ the statement is true then we prove for $P (k+1,l) $ or $P (k,l+1)$ with the help of the assumption. Will be the proof correct??

I assumed all the $P (x,y) $ upto $x=k$ and $y=l $

2

There are 2 best solutions below

0
On

If you've only proved $P(k,l)\to P(k+1,l)$, then given that you've verified $P(1,1)$, you get $P(2,1)$ but you don't automatically get $P(1,2)$.

On the other hand, suppose $P(1,1)$ has been verified, and suppose you've proved both $P(k,l)\to P(k+1,l)$ and $P(k,l)\to P(k,l+1)$.

Let $m,n$ be positive integers.

Starting with $P(1,1)$ and using (in any order) the implication $$P(k,l)\to P(k+1,l)\;\;\;m-1\;\text{times}$$ and the implication $$P(k,l)\to P(k,l+1)\;\;\;n-1\;\text{times}$$ you obtain $P(m,n)$.

It's analogous to moving from the point $(1,1)$ to the point $(m,n)$ using (in any order) $m-1$ unit steps to the right and $n-1$ unit steps up.

Thus if you have $P(1,1)$ and both implications $P(k,l)\to P(k+1,l)$ and $P(k,l)\to P(k,l+1)$, it follows that $P(m,n)$ holds for all positive integers $m,n$.

0
On

Having $P(1,1)$ true we could also use the following technique.

If we prove it $\forall x>0$ whenever $P(x,l)$ is true then $P(x,l+1)$ is also true, we will have the induction in single variable ($l$) now and it'll help us conclude $P(x,y)$ is true for all positive $x,y$. Similar argument goes if we prove for all y with recursion in x.