Hacker News new | past | comments | ask | show | jobs | submit login

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.

There are actually perfectly routine ways to discover formulas like this one for this type of equation. See http://en.wikipedia.org/wiki/Recurrence_relation for some of the theory behind how to do it.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact