Prove using induction: Given a directed graph like the one in the picture and a function $F(x,y)$ that returns the number of simple directed paths between vertex $(0,0)$ and vertex $(x,y)$, prove $F(x,y) = C_{y}^{x+y}$

enter image description here

I'm stuck in the final part of the proof. I know how to prove it w/o induction, but my assignment forces me to use induction.

I will use double induction.

  • Base case: $x=0$ and $y=0$:

It's easy to see that the number of simple directed paths from $(0,0)$ to $(0,0)$ is $1$, then $F(0,0)=1$.


  • Induction hypothesis:

$F(x,0)=C_0^x$ (Next step would be proving it for $x+1$)

$F(x,y)=C_y^{x+y}=C_x^{x+y}$ (since $C_y^{x+y}=C_x^{x+y}$) (Next step would be proving it for $y+1$)

  • Proof for $x+1$:

It's true that $C_0^{x+1}=1$, furthermore, from $(0,0)$ to $(x+1,0)$ there's only $1$ simple path, the one that goes from $(0,0)$ to $(x,0)$ together with edge $((x,0),(x+1,0))$, thus $F(x+1,0)=1=C_0^{x+1}.$

  • Proof for $y+1$:

I have to prove $F(x,y+1)=C_{y+1}^{x+y+1}$ or $F(x,y+1)=C_x^{x+y+1}$

This is where I get stuck.

If you check the graph in the picture, when you turn it 135° you can notice the number of paths from $(0,0)$ to each vertex describes a Pascal's Triangle; this means that $F(m,n)=F(m-1,n)+F(m,n-1)$ (a conclusion I derive from Pascal's rule), so $$F(x,y+1)=F(x-1,y+1)+F(x,y)$$ This is exactly the equation that is giving me trouble... $F(x,y)=C_y^{x+y}$ by induction hypothesis, but I can't turn $F(x-1,y+1)$ into a combinatoric because it's still has a $y+1$ in it, so I'm only left with $F(x-1,y+1)$ which has no algebraic backing, it's just the number of paths from $(0,0)$ to $(x-1,y+1)$. I've been wrapping my head around this for days now, but I'm still stuck.

  • What I mean with "simple directed path" is something like the one highlighted in pink, which is a simple directed path from $(0,0)$ to $(3,4)$... the only allowed directions are right and up.

enter image description here

  • 2
    $\begingroup$ Do a whole row of Pascal's triangle at a time: prove it by induction on $x+y$ instead. $\endgroup$ Aug 30, 2020 at 8:29
  • $\begingroup$ @BrianM.Scott I understand what you are trying to do, that way I would have F(x-1,y+1) since I'm not proving it using horizontal lines, but diagonals. However, I get stuck when trying to write the induction hypothesis, since when assuming $x+y=k$, I can't express $F(x,y)=C_{y}^{x+y}$ according to that. Could you expand further, please? Thanks $\endgroup$ Aug 30, 2020 at 18:21
  • 1
    $\begingroup$ Your induction hypothesis would be: for each $k\in\{0,1,\ldots,n\}$, $F(n-k,k)=\binom{n}k$. $\endgroup$ Aug 30, 2020 at 18:29


You must log in to answer this question.