Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: deprecated: mathematics

Topic: catalan numbers and fibonacci numbers

view this post on Zulip GhaS Shee (Apr 06 2021 at 09:08):

It might be famous that nth fibonacci number fibn fib_n can be solved with complex analysis.
we get nth fibonnaci number just by dumping f(z)=−zz2+z−1f(z) = \frac{-z}{z^2 + z - 1} to the residue calculus.
( We might get fibn=1αn(α−β)+1βn(β−α) fib_n = \frac{1}{\alpha^n(\alpha-\beta)} + \frac{1}{\beta^n(\beta-\alpha)} where α,β\alpha, \beta are zeros of z2+z−1 z^2 + z - 1 . )
How about catalan numbers ?
It there a way of solving c(z)=1−1−4z2z c(z) = \frac{1-\sqrt{1-4z}}{2z} and getting the nth catalan number catalncatal_n in complex analysis ?

view this post on Zulip GhaS Shee (Apr 06 2021 at 09:39):

I might get the instruction from this stackexchange. (Excuse me for the interruption.)

view this post on Zulip John Baez (Apr 06 2021 at 15:00):

You can estimate the growth rate of the Catalan numbers by applying the Cauchy-Hadamard theorem to the function

c(z)=1−1−4z2z \displaystyle{ c(z) = \frac{1 - \sqrt{1 - 4z}}{2z} }

But it's much harder, maybe impossible to get an exact formula this way. The Fibonacci generating function f(z)f(z) is a rational function, so you can estimate the growth rate of the Fibonacci numbers by using Cauchy-Hadamard, which only cares about the pole closest to the origin, and get an exact formula by keeping track of both poles. But c(z)c(z) has a branch cut so it's much more complicated.

view this post on Zulip John Baez (Apr 06 2021 at 15:04):

If you want to learn a lot about these techniques, read this:

view this post on Zulip John Baez (Apr 06 2021 at 15:06):

See part B, "Complex asymptotics", and especially section IV.3, "Singularities and exponential growth of coefficients", and the sections after that.

view this post on Zulip John Baez (Apr 06 2021 at 15:06):

It's a great book if you're interested in applying complex analysis to combinatorics.

view this post on Zulip GhaS Shee (Apr 06 2021 at 15:49):

@John Baez Thank you! The book sounds what I would like to read very much :heart_eyes: