- #1
dancergirlie
- 200
- 0
Homework Statement
A triangulation of a convex polygon is a decomposition of the polygon into
triangles whose interiors do not overlap and whose vertices lie at vertices of
the polygon. Prove that there are Cn−2 ways to triangulate an n-sided convex
polygon
Homework Equations
cn= (1/2)(2n choose n)
The Attempt at a Solution
I tried a proof by induction:
let n=3.
there is only one way to triangulate a triangle, and
cn-2=c1=(1/2)(2 choose 1)=1. So the statement holds for n=3
now assume the statement holds for n=k
So the number of ways to triangulate a k-sided polygon is Ck-2=(1/2)(2(k-2) choose k-2)
Now let n=k+1
This is where I get stuck and I dont' know what to do... any help/hints would be appreciated.