Proof using mathematical Induction Suppose I am proving the statement $P(m,n)$ in natural numbers.
Steps:
1) Proving $P(1,1)$ true
2) $P(m,n) \implies P(m+1,n)$
My doubt while proving second step is that, can I assume $P(m,1), P(m,2),\cdots P(m,n)$ are true or I have to prove by taking $n$ as constant (using $P(m,n)$ only)? 
Suppose I prove step 2, then
3) $P(m,n) \implies P(m,n+1)$
Here can I assume $P(m-1,n+1)$ as true?
 A: If $X$ is a set that is well-ordered by some ordering relation $<$, then you can prove a property $Q(x)$ by induction on $x$, by showing that for any $x \in X$, if $Q(y)$ holds for every $y < x$, then $Q(x)$ holds.
This is called complete or course-of-values induction when $X$ is the natural numbers with the usual ordering. Peano's principle of induction for the natural numbers asking you to prove that $Q(0)$ holds and that for every $x \in \Bbb{N}$, $Q(x + 1)$ holds if $Q(x)$ holds is a special case.
In your case, $X$ is $\Bbb{N}\times\Bbb{N}$ (the set of pairs of natural numbers $(m, n)$). The induction principle you want to use is justified by considering the lexicographic ordering on $X$: $(m, n) < (m', n')$ iff $m < m'$ or $m = m'$ and $n < n'$.
A: It is easier to figure out the answer by drawing a grid with the first few elements of $\Bbb N\times \Bbb N$.
Given the question you're asking, what you really want to do is proceed by squares: let $T(n)$ denote the proposition

$P(p,q)$ is true for all $p,q$ such that $p\leq n$ and $q\leq n$.

I claim that if you prove what you said, then you can prove that $T(n)\implies T(n+1)$ for all $n$.
What you said you can prove is
$$[P(p,1), P(p,2),\cdots P(p,q)]\implies P(p+1,q)\tag{1}$$
 $$[P(p-1,q+1), P(p,q)] \implies P(p,q+1)\tag{2}$$
I'm assuming here that cases where $p\leq 0$ or $q\leq 0$ are considered vacuously true.
Now assume $T(n)$. 


*

*By $(2)$, you can prove that $P(1,n+1)$ and then $P(p,n+1)$ for all $p\leq n$.

*By applying $(1)$ to every $q$ between $1$ and $n+1$, you get $P(n+1,q)$ for all $q\leq n+1$.


Hence $T(n+1)$ as claimed.
