Which is smaller? which is larger?

Today let us look at the following two tricky questions:

Question 1: Among these two numbers 4444 x 55555 and 5555 x 44444, which one is smaller? which one is larger?


Question 2: How about  5000 x 5000 and 4999 x 5001, which one is smaller? which one is larger?

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.

Complex number

Today we will learn about the complex numbers. The crucial point about complex numbers is that we accept a very special number that we will denote it by $i$. This number $i$ is very special because it satisfies the following identity $$i^2 = -1.$$

So a complex number will have the form $$a + ib$$ where $a$ and $b$ are two real numbers. When $b=0$ then $a + ib = a$ is just a normal real number, and when $a=0$ then $a + ib = ib$ is called a pure imaginary number. Here are some examples of complex numbers: $$1+ i, ~~ 2 - 3i, ~~ -\sqrt{3} + 4i, ~~5i - 4, ~~6, ~~i, ~~-3i, ~~4 + 2i, \dots$$

Power sum and Wolstenholme's theorem

In the last post, we have learned how to derive formulas for the power summation $$S_k(n) = 1^k + 2^k + 3^k + \dots + n^k.$$

Today we will investigate some divisibility properties of the power summation $S_k(n)$. We will prove that if $p$ is a prime number and $k$ is not divisible by $p-1$ then $$S_k(p-1) = 1^k + 2^k + 3^k + \dots + (p-1)^k = 0 \pmod{p}.$$

We will also investigate the following summation $$S_{-k}(n) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{n^k}.$$

There is a theorem in number theory concerning this summation, it is called Wolstenholme's theorem.

Wolstenholme's Theorem. If $p$ is a prime number $>3$ then $$S_{-1}(p-1) = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{p-1} ~=_{Q} ~0 \pmod{p^2} $$ and $$S_{-2}(p-1) = \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \dots + \frac{1}{(p-1)^2} ~=_{Q} ~0 \pmod{p}.$$

We will prove a general result, that is, if $p$ is a prime number and $k$ is not divisible by $p-1$ then $$S_{-k}(p-1) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{(p-1)^k} ~=_{Q} ~0 \pmod{p}.$$

Power sum

Today we will learn about how to derive the formula for power summation $$S_k(n) = 1^k + 2^k + 3^k + \dots + n^k .$$


Our main tool is the following binomial identity
$$(x+y)^k = x^k + {k \choose 1} x^{k-1} y + {k \choose 2} x^{k-2} y^2 + {k \choose 3} x^{k-3} y^3 + \dots + {k \choose {k-1}} x y^{k-1} + y^k.$$

Euclidean algorithm

In previous post, we have learned about Bézout's Lemma. Today, we will learn about Euclidean algorithm. This algorithm is used to determine the coefficients in the Bézout's equation.

Let us recall Bézout's lemma. 

Bézout's Lemma. Let $a$ and $b$ be two integers and $d$ their greatest common divisor. Then there exist two integers $x$ and $y$ such that $$d = a ~x + b ~y.$$

We use Euclidean algorithm to calculate the greatest common divisor $d$ of the two numbers $a$ and $b$, and determine the two values of $x$ and $y$ in Bézout's equation $$d = a ~x + b ~y.$$

We will see that Euclidean algorithm is motivated from a very simple and natural idea.

Bézout's lemma

Today we will learn a very beautiful result in number theory, the Bézout's lemma, it is stated as follows.

Bézout's Lemma. Let $a$ and $b$ be two integers and $d$ their greatest common divisor. Then there exist two integers $x$ and $y$ such that $$d = a x + b y.$$

Another Proof of Wilson's Theorem

In previous posts, we have learned about modulo for rational numbers. To show its application, today, we will use the language of modulo of rationals to give another proof of Wilson's Theorem.

Wilson's theorem is a well known theorem in number theory. It is stated as follows.

Wilson's Theorem. If $p$ is a prime number then $$(p-1)! = -1 \pmod{p}.$$