Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I noticed a while ago that the powers of 1001 encode the successive rows of pascal's triangle/the binomial coefficients. This is not so surprising, since we are effectively taking powers of the polynomial (1+x), but replacing x with 1000 (clearly it works the same if we use any other power of ten instead). I wonder if we can find a relationship to that here. We might start by looking at this relation:

  1/(1-x) = 1 + x + x^2 + x^3 + ...
Hopefully this will yield an operator x whose succesive powers are the fibonacci numbers. Take .01/(1-x) = 1/89, then x = 0.11. Actually, the powers of x, just like 1001 above, will yield rows of pascal's triangle. So the taylor expansion above tells us that F(k) = Σ(n=0..k-1) B(n, k), in other words that each fibonacci number is the sum of a diagonal of pascal's triangle (like here: https://cdn1.byjus.com/wp-content/uploads/2018/11/maths/2016...)

More generally, we can compute numbers with decimal expansions of the fibonacci numbers with 10^-2n / (1 - 10^-n - 10^-2n). Notice that this is just the z-transform of the recurrence relation of the fibonacci series, with 10^n replacing z:

  Z(f(n)) = Z(f(n-1) + f(n-2) + δ(n-2)) (δ is the kronecker delta)
     F(z) = z^-2 / (1 - z^-1 - z^-2)
The taylor expansion of this expression has coefficients equal to the terms of the fibonacci sequence - which makes sense, because that's the definition of the z-transform. We can, with a little rearranging, get an explicit formula for the fibonacci sequence from it too:

  Take φ± = (1 ± √5)/2
  Then F(z) = z^2/(z - φ+)/(z - φ-)
            = ( φ+ z/(z - φ+) - φ- z/(z - φ-) )/√5 (by partial fraction decomposition)
  Z^-1(F(z)) = f(n) = (φ+^(n+1) - φ-^(n+1))/√5


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: