←back to thread

Analytic Combinatorics – A Worked Example

(grossack.site)
105 points mathgenius | 2 comments | 08 Apr 25 17:29 UTC | HN request time: 0.695s | source
Show context
PollardsRho ◴[08 Apr 25 18:37 UTC] No.43625111[source]▶
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"?

replies(3): >>43625353 #>>43626182 #>>43626796 #
sfpotter ◴[08 Apr 25 19:01 UTC] No.43625353[source]▶
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.
replies(2): >>43625380 #>>43625678 #
1. PollardsRho ◴[08 Apr 25 19:03 UTC] No.43625380[source]▶
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.)
replies(1): >>43626760 #
2. paulpauper ◴[08 Apr 25 21:44 UTC] No.43626760[source]▶
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.