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}]$$