Sequence - Part 9

This is the last post of our series; here is the link to "Sequence - Part 1" if you haven't read it. Today we will do some more exercises on sequence. We will prove some interesting identities. For the Pell sequence $$P_0=0, ~~P_1 = 1, ~~P_n = 2 P_{n-1} + P_{n-2},$$ and the companion Pell sequence $$H_0=1, ~~H_1 = 1, ~~H_n = 2 H_{n-1} + H_{n-2},$$ we will show that $$H_n^2 - 2 P_n^2 = (-1)^n.$$
For the Fibonacci sequence $$F_0 = 0, ~~F_1 = 1, ~~F_n = F_{n-1} + F_{n-2},$$ we will prove the following identity $$\frac{F_{2013(n+1)} - F_{2013 (n−1)}}{F_{2013 n}} = \frac{F_{2013(n^{2013}+1)} - F_{2013 (n^{2013}−1)}}{F_{2013 n^{2013}}}.$$

Sequence - Part 8

In the last post, we learn how to determine a trigonometric formula for a sequence in the case when the characteristic equation has complex roots. Today we will solve more exercises for this case.

Sequence - Part 7

This is the 7th part of our series on sequences. Today we will learn how to solve a linear recurrence equation in the case when the characteristic equation has complex roots. In this case, we can express the complex roots of the characteristic equation in trigonometric form and then use de Moivre's identity to obtain a trigonometric formula for the sequence.

Sequence - Part 6

Today we will learn about difference operator and use it to prove a fundamental theorem for linear recurrence equations.

A fundamental theorem for linear recurrence equations. Suppose that the characteristic equation can be factored as $$f(x) = a_k x^k + a_{k-1} x^{k-1} + \dots + a_0 = (x - z)^j (b_s x^s + b_{s-1} x^{s-1} + \dots + b_0)$$ and $$f_n = p(n)~z^n,$$ where $p(n)$ is a polynomial of degree less than $j$. Then the sequence $f_n$ satisfies the recurrence equation 
$$a_k f_{n} + a_{k-1} f_{n-1} + \dots + a_1 f_{n-k+1} + a_0 f_{n-k} = 0.$$

Sequence - Part 5

Today we will go through some examples. The first type of examples involves solving a linear recurrence equation to derive a general formula for a sequence. The second type of examples does the reverse process, in which, we are given a formula of a sequence and asked to determine its recurrence equation.

Sequence - Part 4

Today we will learn how to solve a linear recurrence equation and derive a general formula for a sequence. This method will work for all cases, including the case when the characteristic equation has multiple roots.  

Sequence - Part 3

This is the third part of our series on sequences. There will be no new material in this post. The main purpose of this post is to go through some examples so we can get used to the method of solving recurrence equations. If you have not read the previous parts of our series, please read them here: Part 1, Part 2.

Sequence - Part 2

This is the second part of our series on sequences. Please have a careful read of Part 1 before you continue to this post. Today, we will introduce some more terminologies about sequences and we will present a general method to solve a linear recurrence equation.

Sequence - Part 1

Today we will begin our first post of a series on recurrence sequences. The purpose of this series is to show you how to derive a general formula for a sequence that satisfies a linear recurrence equation. We start with some basic operations on sequences. We will learn about addition of sequences and multiplication of a sequence with a number.

Fibonacci sequence and Pascal triangle

In previous post, we used the result of a tile matching puzzle to prove an identity for Fibonacci sequence. Today, we will continue on and prove another identity. We will show that $${2011 \choose 0} + {2010 \choose 1} + {2009 \choose 2}+ {2008 \choose 3}+ \dots + {1007 \choose 1004}+ {1006 \choose 1005} = F_{2012},$$ $${2012 \choose 0} + {2011 \choose 1} + {2010 \choose 2}+ {2009 \choose 3}+ \dots + {1007 \choose 1005}+ {1006 \choose 1006} = F_{2013}.$$
In general, we have the following identity $$\sum_{v+u=n}{v \choose u} = F_{n+1}.$$ Through this identity, we will see an interesting connection between the Fibonacci sequence and the Pascal triangle.

Fibonacci identities

In previous post, we have learnt about Fibonacci sequence and a tile matching puzzle. Today, we will use the result of the tile matching puzzle to prove the following identity on Fibonacci sequence $$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1}.$$

Like an art painting, a mathematical problem reflects different beauties if we view it at different angles. Take, for example, the Fibonacci identity that we are considering, we can prove this identity by different methods. One method is to use the formula $$F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right]$$ to calculate the two sides of the identity and make them equal by straightforward algebraic manipulations. Another method is to make use of the tile matching puzzle that we learned in the previous post. I hope that you will find this "combinatorial" method more interesting.

Fibonacci numbers and a tile matching puzzle

Today we will learn about Fibonacci sequence and a tile matching puzzle. We will soon see that the tile matching puzzle seems to be unrelated to the Fibonacci sequence, but it turns out that the solution to the puzzle is, in fact, the Fibonacci sequence!

Let us first introduce the Fibonacci sequence. The Fibonacci sequence $\{F_n\}$ is determined by the following rule: $$F_0 = 0, ~F_1 = 1, ~F_{n+1} = F_n + F_{n-1}.$$

Thus, $$F_0 = 0, ~F_1 = 1, ~F_2 = 1, ~F_3 = 2, ~F_4 = 3, ~F_5 = 5, ~F_6 = 8, ~F_7 = 13, ~F_8 = 21, \dots$$

de Moivre's formula

In previous post we have learned about complex numbers. Today, we will learn about the trigonometric form of a complex number and the famous de Moivre's formula.

A facebook friendship problem

Do you know that facebook has its own mathematical problem? It is called the facebook friendship problem. Never heard of it?!

Well, this problem is to prove that if you pick out 6 arbitrary people on facebook, then among these 6 people, you can find 3 people such that they are all mutually friend of each other, or there are no friendships among them at all. 

For example, in the figure below, on the left we have 6 people: Amy, Ben, Cindy, Dan, Emma and Francis. If two of them are friend on facebook then we connect them by a purple line, and if they are not friend on facebook then we connect them by a blue line. 

We can see that in this example, we can pick out 3 people, which are Amy, Dan and Emma, they are all mutually friend of each other because they are connected by purple lines. The same is true for Francis, Ben and Cindy.

In the example on the right, we have 6 people: Kate, Linda, Matt, Noah, Olivia and Peter. Among them we can pick out 3 people, which are Olivia, Noah and Matt, there are no friendships among them because they are connected by blue lines. The same is for Peter, Noah and Matt. 

Binomial identity

As we are learning about mathematical induction, in this post, we are going to use induction to prove the following:

• formula for the Pascal's triangle $$p_{n,k} = {n \choose k} = \frac{n!}{k! (n-k)!}$$
• the binomial identity $$(x+y)^n = x^n + {n \choose 1} x^{n-1} y + {n \choose 2} x^{n-2} y^2 + \dots + {n \choose {n-2}} x^{2} y^{n-2} + {n \choose {n-1}} x y^{n-1} + y^n$$