MathDB

Let

X

be the set of all lattice points in the plane (points

(x, y)

with

x, y \in \mathbb{Z}

). A path of length

n

is a chain

(P_0, P_1, ... , P_n)

of points in

X

such that

P_{i-1}P_i = 1

for

i = 1, ... , n

. Let

F(n)

be the number of distinct paths beginning in

P_0=(0,0)

and ending in any point

P_n

on line

y = 0

. Prove that

F(n) = \binom{2n}{n}

Problem Statement