[eutectic]

The generating function proof is also really beautiful! I think I maybe like it even more than the linear algebra proof.

[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.