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.
