13 ms·
Very nice. This is similar to Donald Knuth’s treatment in §1.2.8 of v.I of The Art of Computer Programming (Fundamental Algorithms).
by leephillips 5y ago
Very nice. This is similar to Donald Knuth’s treatment in §1.2.8 of v.I of The Art of Computer Programming (Fundamental Algorithms).
- gjm11 5y agoYup. I don't think the similarity is because I'm copying Knuth (I certainly wasn't deliberately doing so); this is a very well known argument and there isn't all that much scope for presenting it very differently. (Oddly, I think the presentation in the later Concrete Mathematics is worse than in TAOCP; they're trying to make it more approachable but I think just make it a bit more roundabout.)
- leephillips 5y agoOh, absolutely, I realize that. It’s just that I learned this from Knuth so I recognized the derivation, and I thought you’d like to see it, but I see you already know about it.