[kccqzy]

The generating function approach is the standard way of solving recurrences. In that sense, it isn't beautiful, just routine. But yes the first time I'd seen it I felt my body shudder at that sorcery.