Let Sn be the number of lattice paths in the Cartesian plane that start at (0,0), end at (n,n), contain nO points above the line y and are composed only of steps (0,1) , (1,0), and (1,1) , i.e 1,7and 7 So =1 Consider the generating function S(2) := Csnz" _ n=0 Prove that 1 + (x - 1)S() + xS(2)2 = 0.
