3 ms·
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 compli
by sfpotter 2y ago
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.
- PollardsRho 2y agoThey 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.)
- paulpauper 2y agoYes, 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.
- LegionMammal978 2y agoIn 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.
- aleph_minus_one 2y ago> 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).