[tikhonj]

Is this really an "induction-style" algorithm? (I haven't actually heard that term before.) I usually associate induction with taking some large input and shrinking it at each step until you hit some base case. This is really the opposite of induction--it starts with a base case (1) and grows the output, which makes this sound a bit more like co-induction.

Another way to think about it would be that he defined a little finite-state automaton to compute the answer. You just run the automaton for as many steps as you want, noting down what it outputs each time. I think this is actually very much like what a programmer would write if tasked with solving FizzBuzz in an online streaming fashion (rather than for some bounded n).

Maybe it's just my bias towards functional programming showing, but I actually think this approach is fairly intuitive. In fact, I would have probably come up with something structurally similar (differing only in details).

[bcoates]

You're right, it looks like co-induction the term for what I was thinking.

Is it a common FP technique to do local-state-less looping like that? I would expect a tail-recursion solution to pass the next or previous value rather than re-deriving it from reading the output.