Generating functions

Generating functions

Generating functions

Definition

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.

Fibonacci sequence

The generating function

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})\)

Using the definiton of the Fibonacci sequence

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)\)

Reducing the functions

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}\)

Using the first element in the sequence

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})}]\)

Finishing off

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}]\)