This is a fun example. The formula's easy to prove by induction, but discovering it is less obvious and this is an interesting way.

It's the tip of the iceberg though - generatingfunctionology is worth inspecting thoroughly.