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

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

$$C_0^0=1=F(0,0)$$

• 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. • Do a whole row of Pascal's triangle at a time: prove it by induction on $x+y$ instead. Aug 30, 2020 at 8:29
• @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 Aug 30, 2020 at 18:21
• Your induction hypothesis would be: for each $k\in\{0,1,\ldots,n\}$, $F(n-k,k)=\binom{n}k$. Aug 30, 2020 at 18:29