Fibonacci numbers and continued fractions

Fibonacci is probably the most well known sequence in mathematics. Today, we will see how Fibonacci numbers can be used to construct beautiful patterns called continued fractions.

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

1 = 2012 = 2013

In previous posts, we learned about mathematical induction and we used induction to solve some problems. We can see that mathematical induction is a useful technique in problem solving. Today, we will consider two induction proofs that lead to a wrong result that $$1 = 2012 = 2013$$ Let us know if you can identify the wrong steps in the proofs.

Mathematical induction III

Today, we will solve some more problems using mathematical induction.

Problem 7. Observe that $$\cos 2 \alpha = 2 \cos^2 \alpha - 1$$

Prove that we can write $\cos n\alpha$ as a polynomial of $\cos \alpha$.