Two dimensional induction

Question

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?

Answer 1

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$.

Answer 2

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.

Answer 3

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.