A series can be described as:
\(\sum_{i=0}^{\infty }s_i x^i\)
If we know the function equal to this series, we can identify the \(i\)th number.
Let’s use a generating function to create a function for the Fibonacci sequence’s \(c\)th digit. \(F(c)=\sum_{i=c} x^is_i\)
Let’s look at it for other starts:
\(F(c+k)=\sum_{i=c} x^{i+k}s_{i+k}\)
\(F(c+k)=\sum_{i=c+k} x^is_i\)
\(F(c+1)=\sum_{i=c} x^{i+1}s_{i+1}\)
\(F(c+2)=\sum_{i=c} x^{i+2}s_{i+2}\)
This means
\(F(c)x^2+F(c+1)x=\sum_{i=c} x^i s_i x^2 +\sum_{i=c} x^{i+1} s_{i+1} x\)
\(F(c)x^2+F(c+1)x=\sum_{i=c} x^{i+2}s_i+\sum_{i=c} x^{i+2}s_{i+1}\)
\(F(c)x^2+F(c+1)x=\sum_{i=c} x^{i+2}(s_i+s_{i+1})\)
From the definition of the fibonacci sequence, \(s_{i}+s_{i+1}=s_{i+2}\).
\(F(c)x^2+F(c+1)x=\sum_{i=c} x^{i+2}(s_{i+2})\)
\(F(c)x^2+F(c+1)x=F(c+2)\)
Next, we expand out \(F(c+1)\) and \(F(c+2)\).
\(F(c)-F(c+k)=\sum_{i=c} x^i s_i -\sum_{i=c+k} x^i s_i\)
\(F(c)-F(c+k)=\sum^{c+k}_{i=c} x^i s_i\)
\(F(c+k)=F(c)-\sum^{c+k}_{i=c} x^i s_i\)
So:
\(F(c+1)=F(c)-\sum^{c+1}_{i=c} x^i s_i\)
\(F(c+1)=F(c)-x^c s_c\)
\(F(c+2)=F(c)-\sum^{c+2}_{i=c} x^i s_i\)
\(F(c+2)=F(c)-x^{c+1}s_{c+1}-x^c s_c\)
Let’s take our previous equation
\(F(c)x^2+F(c+1)x=F(c+2)\)
\(F(c)x^2+[F(c)-x^c s_c]x=F(c)-x^{c+1}s_{c+1}-x^c s_c\)
\(F(c)x^2+F(c)x-x^{c+1} s_c=F(c)-x^{c+1}s_{c+1}-x^c s_c\)
\(F(c)[x^2+x-1]=x^{c+1}s_c-x^{c+1}s_{c+1}-x^c s_c\)
\(F(c)=\dfrac{x^c s_c + x^{c+1}s_{c+1}-x^{c+1}s_c}{1-x-x^2}\)
For the start of the sequence, \(c=0\), \(s_0=s_1=1\).
\(F(0)=\dfrac{x^0 1 + x - x}{1-x-x^2}\)
\(F(0)=\dfrac{1}{1-x-x^2}\)
Let’s factorise this:
\(F(0)=\dfrac{-1}{(x+\dfrac{1}{2}+\dfrac{\sqrt 5}{2})(x+\dfrac{1}{2}-\dfrac{\sqrt 5}{2})}\)
We can then use partial fraction decomposition
\(\dfrac{1}{(M+\delta)(M-\delta)}=\dfrac{1}{2\delta}[\dfrac{1}{M-\delta}-\dfrac{1}{M+\delta}]\)
To show that
\(F(0)=\dfrac{-1}{\sqrt 5}[\dfrac{1}{x+\dfrac{1}{2}-\dfrac{\sqrt 5}{2}}-\dfrac{1}{x+\dfrac{1}{2}+\dfrac{\sqrt 5}{2}}]\)
\(F(0)=\dfrac{-1}{\sqrt 5}[\dfrac{\dfrac{1}{2}+\dfrac{\sqrt 5}{2}}{(x+\dfrac{1}{2}-\dfrac{\sqrt 5}{2})(\dfrac{1}{2}+\dfrac{\sqrt 5}{2})}-\dfrac{\dfrac{1}{2}-\dfrac{\sqrt 5}{2}}{(x+\dfrac{1}{2}+\dfrac{\sqrt 5}{2})(\dfrac{1}{2}-\dfrac{\sqrt 5}{2})}]\)
\(F(0)=\dfrac{-1}{\sqrt 5}[\dfrac{\dfrac{1}{2}+\dfrac{\sqrt 5}{2}}{x(\dfrac{1}{2}+\dfrac{\sqrt 5}{2})-1}-\dfrac{\dfrac{1}{2}-\dfrac{\sqrt 5}{2}}{x(\dfrac{1}{2}-\dfrac{\sqrt 5}{2})-1}]\)
\(F(0)=\dfrac{1}{\sqrt 5}[(\dfrac{1}{2}+\dfrac{\sqrt 5}{2})\dfrac{1}{1-x(\dfrac{1}{2}+\dfrac{\sqrt 5}{2})}-(\dfrac{1}{2}-\dfrac{\sqrt 5}{2})\dfrac{1}{1-x(\dfrac{1}{2}-\dfrac{\sqrt 5}{2})}]\)
As we know
\(\dfrac{1}{1-x}=\sum_{i=0}x^i\)
So
\(F(0)=\dfrac{1}{\sqrt 5}[(\dfrac{1}{2}+\dfrac{\sqrt 5}{2})\sum_{i=0} x^i(\dfrac{1}{2}+\dfrac{\sqrt 5}{2})^i -(\dfrac{1}{2}-\dfrac{\sqrt 5}{2})\sum_{i=0}x^i(\dfrac{1}{2}-\dfrac{\sqrt 5}{2})^i]\)
\(F(0)=\dfrac{1}{\sqrt 5}[\sum_{i=0} x^i(\dfrac{1}{2}+\dfrac{\sqrt 5}{2})^{i+1} -\sum_{i=0}x^i(\dfrac{1}{2}-\dfrac{\sqrt 5}{2})^{i+1}]\)
\(F(0)=\dfrac{1}{\sqrt 5}\sum_{i=0} x^i[(\dfrac{1}{2}+\dfrac{\sqrt 5}{2})^{i+1} -(\dfrac{1}{2}-\dfrac{\sqrt 5}{2})^{i+1}]\)
So the \(n\)th number in the sequence (treating \(n=1\) as the first number) is:
\(\dfrac{1}{\sqrt 5}[(\dfrac{1}{2}+\dfrac{\sqrt 5}{2})^{n} -(\dfrac{1}{2}-\dfrac{\sqrt 5}{2})^{n}]\)