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

For a linearly recursive sequence x_0, x_1, x_(n+2) = ax_(n+1) + bx_n, the general formula for the terms is

x_n = cα^n + dβ^n,

where α, β are the roots of the quadratic x²−ax−b; c, d are solutions to the system

c + d = x_0 cα + dβ = x_1.

If the series Σ x_n⋅10^n converges then its value is

10c/(10−α) + 10d/(10−β) = ((100−10a)x_0 + 10x_1)/(100 − 10a − b).

If a, b, x_0, x_1 are all rational then the above series converges to a rational number, too. This is the case for the Fibonacci sequence, with a=b=1, x_0=0 and x_1=1.



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

Search: