Two dimensional induction I have the following problem:
I need to prove that given the following integral
$\int_{0}^{1}{c(k,l)x^k(1-x)^l}dx = 1$,
we the constant $c(k,l) = (k+l+1) {{k+l}\choose{k}} = \frac{(k+l+1)!}{k!l!}$,
with the use of two dimensional mathematical induction on $min(k,l)$. 
Here $k$ and $l$ are two nonnegative integers.
(THUS: I need to proof that $c(k,l)$ is equal to $(k+l+1) {{k+l}\choose{k}}$)
For the base step I have proved that $c(k, 0) = c(0, k) = k + 1$ for all $k$.
I am given a hint that for the induction step I could try using integration by parts to show $c(k,l) = \frac{k+1}{l} c(k+1,l−1)$.
By integrating the following by parts I indeed managed to show the latter:
$\int_{0}^{1}{c(k+1,l-1)x^{k+1}(1-x)^{l-1}dx}=1$.
However, I don't really see how this helps me to complete my proof, since I don't really get the idea of two dimensional induction.
Can someone maybe clarify this a bit for me, and help me further with my proof?
 A: In some sense, I think we don't need two-dimensional induction here. Assume that you showed the recurrence relation
$$
c(k, l) = \frac{k+1}{l}c(k+1, l-1)
$$
by using the integration by parts. Also, we know base case: $c(k, 0) = c(0, k) = k+1$. Then 
$$
c(k, l) = \frac{k+1}{l} c(k+1, l-1) = \frac{k+1}{l} \frac{k+2}{l-1} c(k+2, l-2) \\= \cdots = \frac{(k+1)(k+2)\cdots(k+l)}{l(l-1)\cdots1}c(k+l, 0)= \frac{(k+1)(k+2)\cdots (k+l+1)}{l(l-1)\cdots 2\cdot 1} = \frac{(k+l+1)!}{k!l!}
$$

If you want to use induction, you can write in this way: First, we know $c(k, 0) = k+1$ for all $k$. (This is a base step) 
Assume that $c(k, l) =\frac{(k+l+1)!}{k!l!}$ is true for all $k$ and $l \leq L$. For $l = L+1$, we have
$$
c(k, L+1) = \frac{k+1}{L+1} c(k+1, L) = \frac{k+1}{L+1} \frac{(k+L+2)!}{(k+1)!L!} = \frac{(k+L+2)!}{k!(L+1)!}
$$
so it is also true for $l = L+1$. 
A: Let me give you an intuitive hint on how to deal with 2D induction
 
You have demonstrated that the hypothesis is true on the axis $k=0$, for whichever $l$ in the domain of interest ($[0,\infty )$ in this case).
You have demonstrated that if the hypothesis is true for $(l,k)$ then it is true for $(l-1,k+1)$.
Therefore it is true for the whole diagonal line shown in the sketch, going from $(l,0)$ to $(0,l)$.
Thus, it is true for any  such diagonal line, starting from whichever point $(l,0)$.
These lines cover all the points in $[0, \infty)^2$ and thus the hypothesis is true  over all such a domain.
If the recursion had been $(l,k)\, \to \, (l+1,k+1)$ then it is clear that you should have started from demonstrating that the hypothesis is true on $(l,0)$ and $(0,k)$
to be able to cover all the quadrant.
A: Integration by parts relates $I_{k,l}$ to $I_{k+1,l-1}$. So by setting $l=n-k$, you relate $I_{k,n-k}$ to $I_{k+1,n-(k+1)}$, which forms an ordinary induction on $k$. The $I_{0,n}$ are elementary.
