**Donald Knuth, et al**:

*“The most powerful way to deal with sequences of numbers, …, is to manipulate infinite series that generate those sequences.” – “Concrete Mathematics“*

“…to discover the **equation** in the first place, using the important method of **generating functions**, which is a valuable technique for solving so many problems.” – “*The Art of Computer Programming Volume I*”

**Example:**

Fibonacci sequence: {0, 1, 1, 2, 3, 5, 8, 13…}

Definition of the Fibonacci sequence as a recurrence relation:

This definition is not so useful in computation, we want to find a general term formula in terms of **n**.

**Step 1: Find the generating function F(x)**

The correspondence below:

**Sequence** **Generating Function**

with

**Step 2: Find the closed form of F(x)**

**[A]:**

**[B]:**

**[C]:**

**[A] + [B] – [C]:**

**Left-Hand Side:**

**Right-Hand Side:**

+ …

+ …

From the Recurrence definition above, we know:

and

or,

**Right-Hand Side: ** -x

We get **[A] + [B] – [C]:**

**Step 3: Find the general term Fn**

Now we have a generating function of the Fibonacci **Sequence** F(x) in closed form. We want to express it as an infinite **Series**.

Let’s factorize

Matching term by term on both sides, solve the 4 simultaneous equations with 4 unknowns:

We know in secondary school:

Let u = rx

Similarly,

From the above 2 equations in r, s:

By 趙爽 Zhao Shuang 三国东吴 : 222 AD Chinese Mathematician (1,300 years earlier than Viète, 16th Century French Mathematician) Theorem: r, s are the solutions of the quadratic equation:

We assume r > s,

Verify:

Ref:

**Math Girls** by Hiroshi Yuki et al.

http://www.amazon.co.uk/dp/0983951306/ref=cm_sw_r_udp_awd_UKSvtb1AXNWCE

Reblogged this on Singapore Maths Tuition.