Analytic Combinatorics – A Worked Example

Very cool!

What's meant by "it’s already too much to ask for a closed form for fibonacci numbers"? Binet's formula is usually called a closed form in my experience. Is "closed form" here supposed to mean "closed form we can evaluate without needing arbitrary-precision arithmetic"?

Author probably just unaware of Binet's formula. But I'd agree with their assessment that there's unlikely to be a closed form for the (indeed, much more complicated!) quantity that they're interested in.

They then say there's an approximation for Fibonacci, which makes me think that's what they're calling Binet's formula. (I'd also expect an author with this mathematical sophistication to be aware of Binet's formula, but maybe I'm projecting.)

In fact, for that 'warmup' problem, the leading term has a base and coefficient that are roots of cubic polynomials, given in the OEIS entry. But often the coefficient will be trancendental for these sorts of problems.

> Is "closed form" here supposed to mean "closed form we can evaluate without needing arbitrary-precision arithmetic"?

You don't need arbitrary-precision arithmetic to evaluate Binet's formula - big integer arithmetic suffices (simply do your calculations in the ring Z[X]/(X^2-X-1) ).

Yes, the Binet formula is a closed-form. It arises because of a 2nd order linear recursion , which is not the same as the generating function. Also he confuses the characteristic equation for the generating function. I would recommend a discreate math textbook if you want to learn this.

It is closed form .the author makes so many mistakes here. All linear recusions are closed form by simply finding the roots of the characteristic equation. This is separate from the generating function, which the author confuses with the characteristic equation. A generating function is used when it's not possible to find a closed-form expression.

> But often the coefficient will be tran[s]cendental for these sorts of problems.

What makes you believe that the coefficient will be transcendental? I'd rather expect some non-trivial algebraic number (i.e. root of some polynomial with rational coefficients).

At that point, you'd be better off just using a recursive algorithm like the one in GMP. You're swapping out arbitrary-length for arbitrary-precision.