Fractal Image Compression Based on Iterated Function Theory

Introduction
The development of the Internet and digital imaging necessitates a staggering amount of data to represent modern images. This in turn results in larger storage space and longer time for transmission over computer networks. To address these two problems, there has been a growing interest among researchers and companies in devising effective image compression algorithms. Introduced by Michael Barnsley in 1988, Fractal image compression has been recognised and is now one of the most pervasive coding methods.

History of Fractal Image Compression
In 1982, Benoit B. Mandelbrot, an IBM Mathematician, pioneered a new geometry: fractal geometry. Fractal geometry and traditional geometry differ in that the former can represent the geometry of natural objects such as trees and clouds while the latter cannot. With this emerging branch of mathematics, computer scientists have at their command the tools for simulating artificial but natural looking landscapes. In 1988, Michael Barnsley, the author of Fractals Everywhere, discusses the mathematics of Iterated Function System (IFS) in his book, and proves the Collage Theorem. In essence, the theorem states what an Iterated Function System should be to represent an image. (Barnsley, 1988). This leads one to wonder: in reverse, can an Iterated Function System that generates the original image be constructed from an image? Barnsley proposed that storing images as Iterated Function System can lead to image compression. This is how this idea emerged.

Idea of Fractal Image Compression
Fractal Image Compression (FIC) is an image coding technology rested upon fractal geometry. Natural photographs have redundant information. Some parts are replica of certain parts. As such, they can be altered to imitate a picture that needs to be resized. With fractal image compression, the bit-by-bit storage of the image is represented by an iterated function, resulting in a dramatically less storage.

Iterated Function Systems
IFS theory utilises affine transformations to relate different parts of an image. A combination of rotation, scaling, translation is known as an affine transformation. Using solely such transformations, sophisticated pictures can be defined.

Mathematical notation
$x_{n+1}=a\cdot x_n$ is a scaling transformation. When $0<a<1$, then $x_{n+1}<x_n$ and x is scaled down. When $a>1$, then x is scaled up. Finally, when $-1<a<0$, x jumps back and forth in ever decreasing jumps until it settles at the origin, which is the attractor.
Adding translation is expressed by $x_{n+1}=a\cdot x_n+b$, where b is a real number.
A general form for an affine transformation: $W\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} a&b \\ c&d \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}+\begin{pmatrix} e \\ f \end{pmatrix}=\begin{pmatrix} ax+by+e \\ cx+dy+f \end{pmatrix}$,
where W represents affine transformation.

To find an affine transformation, one needs to find six coefficients a, b, c, d, e and f such that the transformation W obeys: W(original image) ~ desired image. The first step is to introduce x, y coordinate axes. Secondly, randomly choose and mark three points on the original image. Then, mark the respective points on desired image and determine their coordinates.

The coefficients a, b, e can be determined by solving the three linear equations:

$\alpha_1 a+\alpha_2 b+e=\widetilde{\alpha_1}$

$\beta_1 a+\beta_2 b+e=\widetilde{\beta_1}$

$\gamma_1 a+\gamma_2 b+e=\widetilde{\gamma_1}$

The coefficients c, d, f are found similarly from the following equations:

$\alpha_1 c+\alpha_2 d+f=\widetilde{\alpha_2}$

$\beta_1 c+\beta_2 d+f=\widetilde{\beta_2}$

$\gamma_1 c+\gamma_2 d+f=\widetilde{\gamma_2}$

Equation solvers such as TK Solver Plus or Eureka can be used to find the coefficient values.

Traditional way of Fractal Image Compression
1. Dividing the image – Divide it into large and small blocks: N non-overlapping range blocks R_i and M domain blocks D_i that can overlap with others. Those N range blocks should cover the whole image.

2. Matching – For each range block R_i, find a suitable domain block D_i such that after applying a contractive transformation W_i, it resembles R_i. In other words, W_i(D_i) = R_i.

3. Encoding – Find the best match D_i for each R_i. Store the locations of D_i and R_i, and the parameters of W_i. The goal is to find D_i and R_i by minimizing the distance between them.

4. Decoding – Start with a random image which has the same size as the compressed image, and decode it. For a chosen M domain blocks D_i, use a respective contractive transformation. This is the first iteration. In practice, the image will become stable after around ten iterations. When the attractor or final image is reached, the encoded image has been decoded. 

Introduction to fractals

HKCEE 2002 Q13

Interesting fact: this figure is related to fractals.

Steps in the construction of the Koch curve

Fractals are ubiquitous. Unbeknown to most students, such geometric objects can be applied in many disciplines, offering scientists and artists alike limitless exploration. In this post, I will introduce fractals to you.

Small pieces resemble the whole.

A fractal is an image with an infinite amount of of self-similarity, meaning that if you keep zooming in on such an object, you will see the same shape repeated endlessly, as seen in the figure above. 

Terminologies related to fractals:

Iterated function

Basic idea: Start with an input. Then take the output as the next input. Repeat this process several times.

Say we have a squaring function $f(x)=x^2$.

$3  \stackrel{f}{\rightarrow} 9 \stackrel{f}{\rightarrow} 81 \stackrel{f}{\rightarrow} 6561 \cdots$

initial condition/seed (denoted by $x_0$): the number we start with, 3 in this case

Iterating a function produces a sequence of numbers which is called an itinerary/orbit. (This is consistent with the everyday usage of the term; an itinerary is a list, in order, of all the places visited along a journey.)

Notation:

$x_1=f(x_0)$

$x_2=f(x_1)=f(f(x_0))$

$x_3=f(x_2)=f(f(f(x_0)))$

           $\vdots$

$x_{11}=f(f(f(f(f(f(f(f(f(f(f(x_0)))))))))))$

A better notation would be:

$f(f(x))=f^{(2)}(x)$

$f(f(f(x)))=f^{(3)}(x)$

In general, for n applications of f:

$\stackrel{\text{n times}}{f(f(f(\cdots f(x))))}=f^{(n)}(x)$

Note: Don't mix it up with derivatives.

Why Iteration?

Affine Transformations

Fixed points

Julia sets

Dynamical systems

Vector Quantization

[later]

Applications:

Computer Science:

Computer graphics

- simulate photo-realistic landscapes and scenery used in films and video games

- model organic objects and textures such as clouds, trees, fog, and water

Image compression

- scale down size of images to reduce the savings in space (The Compression ratio is huge since the compressed file is represented by an iterated function that requires dramatically less storage.)

Economics:

- demonstrate how the activity of markets accelerates and decelerates: the essence of volatility

- analyze the trend of shares on the stock market based on multifractals

- predict the future behaviour of share prices by studying variations in the past

- elucidate sophisticated economics phenomena

Science:

- measure the variation between normal and diseased structures

- construct fractal antennas

Management:

- manage industrial supply chains and transport systems

More to explore:
Chaos Theory

http://ecademy.agnesscott.edu/~lriddle/ifs/kcurve/kcurve.htm

Fractals in architecture

Fractals in finance 1

Fractals in finance 2

Binomial Theorem

Binomial Expansion
We can apply differentiation to find a certain term of an expansion.

Example:
Find the coefficient of $x^3$ in $\Large \frac{1}{\sqrt{x}(2+\sqrt{x})^3}$.

Conventional method:
$$\begin{align}\dfrac{1}{\sqrt{x}(2+\sqrt{x})^3}&=\dfrac{1}{8\sqrt{x}(1+\frac{\sqrt x}{2})^3}\\
\dfrac{1}{(1+x)^3}&=\sum_{k=0}^{\infty}\binom{-3}{k}x^k=1-3x+6x^2-10x^3+30x^4-\cdots\\ \dfrac{1}{(1+\frac{\sqrt x}{2})^3}&=1-3\frac{\sqrt{x}}{2}+3\frac{x^2}{2}-\cdots\\ \dfrac{1}{8\sqrt{x}(1+\frac{\sqrt x}{2})^3}&=\frac{1}{8\sqrt{x}}(1-3\frac{\sqrt{x}}{2}+3\frac{x^2}{2}-\cdots)\end{align}$$ coefficient of $x^3$ of the given expression $=\dfrac{1}{8} \cdot \binom{-3}{7}\cdot \dfrac{1}{2^7}\\
=\dfrac{1}{8} \cdot \binom{9}{7}\cdot \dfrac{1}{2^7}\\
=-\dfrac{9}{256}$
[In general, $\binom{-n}{k}=(-1)^k\binom{n+k-1}{k}$]

Differentiation:
$$\begin{align}\frac{1}{1+x}&=\sum(-x)^k\\
-\frac{1}{(1+x)^2}&=-\sum(k+1)(-x)^k\\
\frac{2}{(1+x)^3}&=\sum(k+2)(k+1)(-x)^k\\
\frac{1}{(1+x)^3}&=\frac{1}{2}\sum(k+2)(k+1)(-\frac{\sqrt{x}}{2})^k\\
\frac{1}{8\sqrt{x}(1+x)^3}&=\frac{1}{16\sqrt{x}}\sum(k+2)(k+1)(-\frac{\sqrt{x}}{2})^k\\
&=\ldots+\frac{1}{16}(7+2)(7+1)(-\frac{1}{2})^7x^3+\ldots\end{align}$$ coefficient of $x^3=-\dfrac{9}{256}$

Trigonometry

Proof of sum and product of sine and cosine
Recall $e^{ix}=\cos x+i\sin x$
$e^{i(x+y)}=\cos (x+y)+i\sin (x+y)$
$e^{ix}\cdot e^{iy}\\
=(\cos x+i\sin x)(\cos y+i\sin y)\\
=\cos x \cos y -\sin x \sin y+i(\sin x \cos y+\sin y \cos x)\\
\cos x \cos y -\sin x \sin y+i(\sin x \cos y+\sin y \cos x)=\cos (x+y)+i\sin (x+y)$

Comparing the real and imaginary part respectively,
$\cos (x+y)=\cos x \cos y -\sin x \sin y\\
\sin (x+y)=\sin x \cos y+\sin y \cos x\\$
Similarly,
$\cos (x-y)=\cos x \cos y +\sin x \sin y\\
\sin (x-y)=\sin x \cos y-\sin y \cos x$

Then,
$\cos (x+y)+\cos (x-y)=2\cos x \cos y\\
\sin (x+y)+\sin (x-y)=2\sin x \cos y\\
\cos (x+y)-\cos (x-y)=-2\sin x \sin y\\
\sin (x+y)-\sin (x-y)=2\sin y \cos x$,

or equivalently

[Let A = x+y, B = x-y; x = $\frac{A+B}{2}$, y = $\frac{A-B}{2}$]

$\cos A+\cos B=2\cos \frac{A+B}{2} \cos \frac{A-B}{2}\\
\sin A+\sin B=2\sin \frac{A+B}{2} \cos \frac{A-B}{2}\\
\cos A-\cos B=-2\sin \frac{A+B}{2} \sin \frac{A-B}{2}\\
\sin A-\sin B=2\sin \frac{A-B}{2} \cos \frac{A+B}{2}$

Proving trigonometric identities
Example:
Prove $\Large \frac{\sec \theta+\csc \theta}{1+\cot^2 \theta}=\frac{\sec \theta+2\sin \theta}{1+\cot \theta}$.



The proof from LHS to RHS is similar. A third way is to prove LHS - RHS = 0.

Geometric/graphical proof
[later]

When to reject solutions
If $\csc \theta+7\cot \theta=4$, where $0<\theta<\pi$, find $\theta$.
$\csc \theta+7\cot \theta=4$
$7\cot \theta=4-\csc \theta$
$49\cot^2 \theta=16-8\csc \theta+\csc^2 \theta$
$49(1-\csc^2 \theta)=16-8\csc \theta+\csc^2 \theta$
$48\csc^2 \theta+8\csc \theta-65=0$
$\Large \csc \theta=\frac{13}{12}, \frac{-5}{4}$ (rejected because sin > 0 when $0<\theta<\pi$)
$\sin \theta = \frac{12}{13}$
$\theta$ = 1.18 or 1.97 (rejected because $\cot \theta > 0$, meaning $\theta$ is in quadrant I.)

---

It is given that $\sin \theta+\cos \theta=\frac{7}{13}$, where $\frac{\pi}{2} < \theta < \pi$.
Then $\sin \theta-\cos \theta=\frac{17}{13}$
Find  $\sin \theta$ and  $\cos \theta$.

Method I:
$\sin \theta=\frac{1}{2}[(\sin \theta+\cos \theta)+(\sin \theta-\cos \theta)]=\frac{12}{13}$
$\cos \theta=\frac{-5}{13}$

Method II:
$\sin \theta - \cos \theta=\frac{17}{13}$
$\sin^2 \theta = (\frac{17}{13}+\cos \theta)^2$
...
$\cos \theta = \frac{-5}{13} or \frac{-12}{13}$
when $\cos \theta=\frac{-5}{13}, \sin \theta=\frac{12}{13}$
when $\cos \theta=\frac{-12}{13}, \sin \theta=\frac{5}{13}$ (rejected because $\sin \theta+\cos \theta=\frac{7}{13}$, which implies $\sin \theta >1$.)

Moral of the story: Always check the solutions!

[pending] area, eq, s=rθ, a = ½ r^2θ, prove formulas, geometry, application

Proof without M.I.

Sum of squares of n natural numbers
Key idea: n³ - (n-1)³ = 3n² - 3n + 1

1³ - 0³ = 3⋅1² - 3⋅1 + 1
2³ - 1³ = 3⋅2² - 3⋅2 + 1
3³ - 2³ = 3⋅3² - 3⋅3 + 1
...
n³ - (n-1)³ = 3⋅n² - 3⋅n + 1
[Summing all these up]
n³ = 3(1² + 2² + 3² + ... + n²) - 3(1 + 2 + 3 + ... + n) + (1 + 1 + 1 + ... + 1)
Denote 1² + 2² + 3² + ... + n² by S.
n³ = 3S - 3 ½ n(n+1) + n
6S = 2n³ + 3n² + n
$S = \frac{n(n+1)(2n+1)}{6}$

Similarly, you can find the sum of cubes of n natural numbers.

M.I. Divisibility problems

In your mathematics textbook on Mathematical Induction, you should have seen many problems like these:

Prove by M.I. that
$9^n-4^n$ is divisible by 5.
$5^n-1$ is divisible by 4.
$7^n-5^n$ is divisible by 2, etc.

Now do you notice something? It seems that $a-b \vert a^n-b^n$, that is, $a-b$ divides $a^n-b^n$.

In fact, you're right. There is an identity: $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+...+b^{n-1})$
(Expand RHS to see they are equal.)

More interestingly, this is related to modular arithmetic.
$a \equiv b$ (mod a-b)
$a^n \equiv b^n$ (mod a-b)
$a^n-b^n \equiv 0$ (mod a-b)
This implies that $a^n-b^n$ is divisible by a-b.

A problem on curve sketching

I came across an interesting problem on curve sketching a few weeks ago.

Question:


From the first two given information, we know f(x) is continuous at x=0, with value 1. From the third, we know f(x) is not differentiable at x=0, meaning we should expect a cusp at x=0. The slopes -1 and 1 should be noted as well. Using the last piece of information, horizontal asymptote: y=2. (?) f(x) also has to be an even function.

Now, sketching the curve is straightforward, but can we find functions that fit the above requirements?

We know the graph should look something like this.

First, look for functions with horizontal asymptote, examples being $\frac{1}{x^2+1}$ and arctan x. However, we can rule out $\frac{1}{x^2+1}$ because it does not fulfill the 3rd requirement as $\lim_{h \to 0} \frac{f(h)-f(0)}{h} = 0$. We now try f(x) = arctan x. To reach the desired graph, we need to transform the graph. $f(0)=1 \Rightarrow y=\arctan x +1$

Before we continue...

Prerequisite knowledge:
Range of arctan x
Since tan x would not be a function if inverted, only one cycle of tan x is used when finding its inverse, arctan x. The cycle that includes (0, 0) is chosen such that for tan x, domain: $(-\frac{\pi}{2}, \frac{\pi}{2})$ and range: (-∞, ∞) So for its inverse, domain: (-∞, ∞), range:$(-\frac{\pi}{2}, \frac{\pi}{2})$

Now, we want $\lim_{x \to \pm \infty}f(x)=2$, since the upper bound is $\frac{\pi}{2}$ $(\lim_{x \to +\infty} \arctan x=\frac{\pi}{2})$, multiply arctan x by $\frac{2}{\pi}\Rightarrow \frac{2}{\pi}\arctan (ax)+1$. Yet another requirement: f'(0)=1, $f'(x)=\frac{2}{\pi}\frac{a}{1+(ax)^2} \Rightarrow$ set $a=\frac{\pi}{2}$. Finally, $f(x)=\frac{2}{\pi}\arctan (\frac{\pi x}{2})+1$. Since it has to be an even function, we define $f(x)$ to be a piecewise function:

$$f(x)=
\begin{cases}
\frac{2}{\pi}\arctan (\frac{\pi x}{2})+1 & x \geq 0 \\
-\frac{2}{\pi}\arctan (\frac{\pi x}{2})+1 & x<0
\end{cases}$$

My question:
What are other functions that meet the 5 requirements?

Interesting Graphs: Wave

Interestingly, there are mathematical equations that describe waves.

We all know that sine and cosine functions are wave-like functions. One fact you may not know is that a rational function can look like a single pulse wave! [Edited on 26.1: Just discovered another function that resembles a wave: $e^{-x^2}$!]

In general, $y=\dfrac{a}{x^2+b}$ looks like a pulse centered at $x=0$, where $a,b$ are positive real numbers $\neq 0$.

Question: Why does it have to be "+b"?

Having learnt transformation of graphs, we know that $f(x-a)$ is formed by translating $f(x)$ to the right a units; $f(x+a)$ to the left a units, where $a>0$.

For waves,

$y(x, t) = f(x-vt)$ $\Rightarrow$ wave travelling to the right with speed v,

$y(x, t) = f(x+vt)$ $\Rightarrow$ wave travelling to the left with speed v.

Example:

$f(x) = \dfrac{5}{x^2+1}$
"Purple wave": $f(x-vt)$
"Orange wave": $-f(x+vt)$

The "purple wave" is moving to the right, where the "orange wave" is moving to the left. In this case, $v=5$, $t=1$ or $v=1$, $t=5$.

Demonstration of Constructive Interference

For simplicity, choose $v=1$.

At $t=1$,

"Green wave": moving to the right
$y=\dfrac{5}{(x-1+10)^2+1}$
There has to be $\pm$constant, in this case, +10, because otherwise we won't have constructive interference.

"Blue wave": moving to the left

At $t=5$, we have constructive interference: superposition of two waves (represented by the green curve).

$\dfrac{10}{(x+5)^2+1} = \dfrac{5}{(x-5+10)^2+1} + \dfrac{5}{(x+5)^2+1}$

At $t=10$,

"Green wave": moving to the right

"Blue wave": moving to the left

Demonstration of Destructive Interference

Destructive interference: The two waves cancel out each other.

For your information:

Cauchy distribution

The simplest Cauchy distribution is called the standard Cauchy distribution. It is the distribution of a random variable that is the ratio of two independent standard normal variables and has the probability density function $$f(x;0,1)=\dfrac{1}{\pi(1+x^2)}.$$

Its cumulative distribution function has the shape of $\arctan x$:

$$F(x;0,1)=\frac{1}{\pi}\arctan x+\frac{1}{2}.$$

Vieta's formula

Prerequisite knowledge:
Elementary symmetric functions:
$\sigma_k$ of n variables is the sum of all products of k variable(s)

For two variables x, y:
$\sigma_1 = x + y\\
\sigma_2 = xy$

For three variables x, y, z:
$\sigma_1 = x + y + z\\
\sigma_2 = xy + xz + yz\\
\sigma_3 = xyz$

---

From our knowledge of secondary school maths on quadratic functions, we know that for a quadratic equation $ax^2+bx+c$, the sum of roots is given by -b/a whereas the product of roots is c/a.
This is easily proved as follows:
Let p, q be the two roots.
$ax^2+bx+c=0\\
x^2+\frac{bx}{a}+\frac{c}{a}=0 \:[1]\\
(x-p)(x-q)=0\\
x^2-(p+q)x+pq=0 \:[2]$
Comparing [1] and [2], we get the desired result.

In fact, this is related to Vieta's formula, which states that
$\sigma_k = (-1)^k \cdot \frac{a_{n-k}}{a_n}$ for $1\leq k\leq n$.
Proof by MI:
When $n=1$ (degree 1), $f(x)=a_{1}x+a_0$, with one root $-\frac{a_0}{a_1}$.
$\sigma_1=(-1)^1 \cdot \frac{a_0}{a_1}=-\frac{a_0}{a_1}$, as desired.
Assume the formula is true for $n=k$.
When $n=k+1$, $f(x)=a_{k+1}x^{k+1}+a_{k}x^{k}+...+a_0$
Let $g(x)$ be a monic polynomial (coefficient of degree being 1) with degree $k$ (To use our assumption) such that
$f(x)=a_{k+1}(x-r_{k+1})g(x)$, where $r_{k+1}$ is one of the $k+1$ roots of $f(x)=0$.
Then $g(x)=x^k-\sigma_1 x^{k-1}+\sigma_2 x^{k-2}-...+(-1)^k \sigma_k$
Thus $f(x)=a_{k+1}(x-r_{k+1})(x^k-(r_1+r_2+...+r_k)x^{k-1}+...+(-1)^k (r_{1}r_{2}\ldots r_{k}))$
$f(x)=a_{k+1}(x^{k+1}-(r_1+r_2+...+r_k+r_{k+1})x^{k-1}+...+(-1)^k (r_{1}r_{2}\ldots r_{k}r_{k+1}))$
$f(x)=a_{k+1}(x^{k+1}-\sigma_1 x^{k}+...+(-1)^{k+1} \sigma_{k+1}) \: \Box$

Examples:
[later]

A fast method of finding determinant

Prerequisite knowledge:
Properties of determinant

For 3x3 determinant:

Prove it yourself or refer to the website below [p6,7].

Examples:
$$\begin{vmatrix}2&4&1\\4&-3&2\\-1&3&-2\end{vmatrix}=\dfrac{1}{2}\begin{vmatrix}-22&0\\10&-3\end{vmatrix}=33$$ $$\begin{vmatrix}4&5&-2\\-7&-4&-5\\-6&2&1\end{vmatrix}=\dfrac{1}{4}\begin{vmatrix}19&-34\\38&-8\end{vmatrix}=\dfrac{19}{2}\begin{vmatrix}1&-17\\2&-4\end{vmatrix}=15\cdot 19=285$$ $$\begin{vmatrix}a+b&a&a\\a&a+b&a\\a&a&a+b\end{vmatrix}=\begin{vmatrix}b&0&-b\\0&b&-b\\a&a&a+b\end{vmatrix}=\dfrac{1}{b}\begin{vmatrix}b^2&-b^2\\ab&b^2+2ab\end{vmatrix}=b^2\begin{vmatrix}1&-1\\a&2a+b\end{vmatrix}=b^2(3a+b)$$

The formula can be generalised as follows:

Reference

De Moivre's formula

Prerequisite knowledge:
Expressing $e^x, \sin(x), \cos(x)$ as infinite series
Basic trigonometry
Complex number
Binomial theorem

$$\begin{align}e^{i\theta}&=1+i\theta+\dfrac{(i\theta)^2}{2!}+\dfrac{(i\theta)^3}{3!}+\dfrac{(i\theta)^4}{4!}+\dfrac{(i\theta)^5}{5!}+\cdots\\
&=1+i\theta-\dfrac{\theta}{2!}-\dfrac{i\theta}{3!}+\dfrac{\theta^4}{4!}+\dfrac{i\theta^5}{5!}+\cdots\\
&=(1-\dfrac{\theta^2}{2!}+\dfrac{\theta^4}{4!}-\cdots)+i(\theta-\dfrac{\theta^3}{3!}+\dfrac{\theta^5}{5!}+\cdots)\\
&=\cos\theta+i\sin\theta \end{align}$$
Similarly, $e^{in\theta}=\cos n\theta+i\sin n\theta=(\cos\theta+i\sin\theta)^n$.

Using Binomial theorem, we have $$\begin{align}&(\cos\theta+i\sin\theta)^n\\&=\cos^n\theta+n\cos^{n-1}\theta\:i\sin\theta+\frac{n(n-1)}{2}\cos^{n-2}\theta\:i^2\sin^2\theta+\cdots\\&=\cos^n\theta-\frac{n(n-1)}{2}\cos^{n-2}\theta\sin^2\theta+\frac{n(n-1)(n-2)(n-3)}{4!}\cos^{n-4}\theta\sin^4\theta+\cdots\\&+i(n\cos^{n-1}\theta\sin\theta-\frac{n(n-1)(n-2)}{3!}\cos^{n-3}\theta\sin^3\theta+\cdots)\\&=\cos n\theta+i\sin n\theta.\end{align}$$ Therefore, $$\begin{cases}\cos n\theta=\cos^n \theta-\frac{n(n-1)}{2}\cos^{n-2}\theta\sin^2\theta+\cdots \\ \sin n\theta=n\cos^{n-1}\theta\sin\theta-\frac{n(n-1)(n-2)}{3!}\cos^{n-3}\theta\sin^3\theta+\cdots.\end{cases}$$

$z=e^{i\theta}=\cos\theta+i\sin\theta,\qquad \frac{1}{z}=e^{-i\theta}=\cos\theta-i\sin\theta\\ z+\frac{1}{z}=2\cos\theta,\qquad (z+\frac{1}{z})^n=2^n\cos^n\theta\\ z-\frac{1}{z}=2i\sin\theta,\qquad (z-\frac{1}{z})^n=i^n\:2^n\sin^n\theta\\ \star z^n+\frac{1}{z^n}=2\cos n\theta\\ \star z^n-\frac{1}{z^n}=2i\sin n\theta$

Application of De Moivre's formula:
1. Proving trigonometric identities
Example 1:


Example 2:


Example 3:
Express $\cos^5 \theta$ in terms of $\cos\theta$.
Recall $$2^n\cos^n\theta=(z+\frac{1}{z})^n.$$
Substitute $n=5$, $$2^5\cos^5\theta=(z+\frac{1}{z})^5.$$
Using Binomial theorem, $$\begin{align}(z+\frac{1}{z})^5&=z^5+5z^3+10z+\frac{10}{z}+\frac{5}{z^3}+\frac{1}{z^5}\\&=z^5+\frac{1}{z^5}+5(z^3+\frac{1}{z^3})+10(z+\frac{1}{z}).\end{align}$$ Therefore, $\cos^5\theta=\dfrac{1}{2^4}(\cos 5\theta+5\cos 3\theta+10 \cos\theta)$.

2. Finding complex roots
[later]

Methods of partial fractions

Partial fractions are useful in the study of discrete maths, control theory, differential equations, and calculus.

Methods:
1. Observation
For simple rational functions, we can guess the partial fraction decomposition.
$$\frac{1}{(x+1)(x+2)} = \frac{1}{x+1} -\frac{1}{x+2} \\ \frac{x}{(x+2)(x+3)} = \frac{3}{x+3} - \frac{2}{x+2}$$
2. Method of undetermined coefficients: solving a system of linear equations
2a. Comparing coefficients

Example:
$$\frac{x^2}{(x-1)(x^2+4)^2}=\frac{A}{x-1}+\frac{Bx+C}{x^2+4}+\frac{Dx+E}{(x^2+4)^2} \\\\ x^2=A(x^2+4)^2+(Bx+C)(x-1)(x^2+4)+(Dx+E)(x-1)$$ Put $x=1$, we have $A=\dfrac{1}{25}$. Now compare the coefficients of $x^4$, $$A+B=0\Rightarrow B=-\frac{1}{25}.$$ Compare the coefficients of $x^3$, $$-B+C=0 \Rightarrow C=-\frac{1}{25}.$$ Compare those of $x^2$, $$8A-C+4B+D=1 \Rightarrow D=1+\frac{4}{25}-\frac{1}{25}-\frac{8}{25}=\frac{4}{5}.$$ Compare the constant term, $$16A-4C-E=0 \Rightarrow E=\frac{16}{25}+\frac{4}{25}=\frac{4}{5}.$$
2b. Substitution
$$\dfrac{x^2+4}{x(x+2)(3x-2)}=\dfrac{A}{x}+\dfrac{B}{x+2}+\dfrac{C}{3x-2}\\x^2+4=A(x+2)(3x-2)+Bx(3x-2)+Cx(x+2)$$Substitute $x=0,-2,\dfrac{2}{3}$, we have $A=-1,B=\dfrac{1}{2},C=\dfrac{5}{2}$ respectively.

2c. Differentiation

3. Heaviside’s cover-up technique (only a shorthand of substitution)

Note: This method does not work all the time. Sometimes, it gives only partial results.

Example:

To find A, cover up the factor $x^2$ and put $x=0$. Similarly, cover up $x+1$ and put $x=-1$ to find B. Finally, subtract $\large \frac{A}{x^2}$ and $\large \frac{B}{x+1}$ from the original rational function to get C. Alternatively, one can differentiate the equation $x-5 = A(x+1) + Bx² + Cx(x+1)$ twice, yielding $0 = 2(B+C) \Rightarrow C = -B = 6$.

This method is essentially substitution. If you multiply both sides by $x^2(x+1)$, you see how it works. This cover-up technique is just an easy way of finding pfd without the fuss of writing many steps.

Example:
$$\frac{5x+6}{(x^2+4)(x-2)} = \frac{Ax+B}{x^2+4} + \frac{C}{x-2}$$ Using the cover-up technique, we know $C = 2$.
Now what we can do is to simplify $\dfrac{5x+6}{(x^2+4)(x-2)}-\dfrac{2}{x-2}$ or solve two simultaneous equations to find A and B. Alternatively, we can express $x^2+4$ as $(x-2i)(x+2i)$ and use the cover-up technique. However, the calculations will be longer and can be more prone to mistakes.

The cover-up method gives partial results too if a linear factor is repeated. It works only for the highest power of the linear factor.

Reference:
http://www.cimt.plymouth.ac.uk/journal/man.pdf
http://meikleriggs.org.uk/CUR/CUR.pdf

4. Limit

Example:
$$\begin{align}F(x)&=\frac{6x-1}{(1+x)(1-3x)^2}=\frac{A}{1+x}+\frac{B}{(1-3x)^2}+\frac{C}{1-3x}\\ A&=\frac{6x-1}{(1-3x)^2}\bigg|_{x=-1}=-\frac{7}{16}\\ B&=\frac{6x-1}{1+x}\bigg|_{x=\frac{1}{3}}=\frac{3}{4}\\ \large 0 &=\lim\limits_{x \to +\infty} \frac{x(6x-1)}{(1+x)(1-3x)^2}\\
& =\lim\limits_{x \to +\infty} (\frac{Ax}{1+x}+\frac{Bx}{(1-3x)^2}+\frac{Cx}{1-3x})\\
&=A-\frac{1}{3}C \\ \therefore C&=3A=-\frac{21}{16}\end{align}$$
5. Keily’s Method (Useful for repeated linear factors)

Example:
$$\begin{align} \frac{3}{(x+1)^2(x+2)}&=\frac{1}{x+1}\frac{3}{(x+1)(x+2)}\\&=\frac{1}{x+1}(\frac{3}{x+1}+\frac{-3}{x+2})\\&=\frac{3}{(x+1)^2}-\frac{3}{(x+1)(x+2)}\\&=\frac{3}{(x+1)^2}-3(\frac{1}{x+1}-\frac{1}{x+2})\\&=\frac{3}{(x+1)^2}-\frac{3}{x+1}+\frac{3}{x+2}\end{align}$$
Reference:
Pages 5, 6

6. Algebraic Identity

Let p(x) be a function and a, b distinct scalars.
$$\frac{1}{(p(x)+a)(p(x)+b)}=\frac{1}{b-a}(\frac{1}{p(x)+a}-\frac{1}{p(x)+b})$$
Example 1:
$$\frac{x}{(x^2+1)(x^2+4)}=\frac{x}{4-1}(\frac{1}{x^2+1}-\frac{1}{x^2+4})=\frac{1}{3}(\frac{x}{x^2+1}-\frac{x}{x^2+4})$$
Example 2:
$$\begin{align}\frac{1}{s^2(s+a)}&=\frac{s+a}{s^2(s^2-a^2)}\\\\
&=\frac{s+a}{a^2}(\frac{1}{s^2-a^2}-\frac{1}{s^2})\\\\
&=\frac{1}{a^2}\frac{1}{s-a}-\frac{1}{a^2}\frac{s+a}{s^2}\\\\
&=\frac{1}{a^2}\frac{1}{s-a}-\frac{1}{a^2}\frac{1}{s}(1+\frac{a}{s})\\\\
&=\frac{1}{a^2}\frac{1}{s-a}-\frac{1}{a^2}\frac{1}{s}-\frac{1}{a}\frac{1}{s^2}\end{align}$$
More methods

7. Algebraic manipulations

Example: $$\begin{align}\bigg(\dfrac{z+1}{z-1}\bigg)^3&=\dfrac{1}{(z-1)^3}[(z-1)+2]^3\\&=1+\dfrac{6}{z-1}+\dfrac{12}{(z-1)^2}+\dfrac{8}{(z-1)^3}\end{align}$$
Application of partial fractions:
1. Integration

2. Differential equations
Inverse Laplace Transform by Partial Fraction Decomposition

Example:

More examples on pages 4-6

Evaluating limits

Conventional methods:
1. Algebraic simplification – cancelling common factors, expanding, multiplying by conjugates
2. Rationalization
3. Trigonometry identities
4. Special limits

$$\lim_{x \to 0} \frac{\sin x}{x} = 1 \\ \\ \lim_{x \to 0} (1+\frac{1}{x})^x = e$$
5. L'Hôpital's rule

$$\lim_{x \to c} \frac{f(x)}{g(x)} = \lim_{x \to c} \frac{f'(x)}{g'(x)}$$
Used only when we have indeterminate forms, i.e. $\frac{0}{0}$, $\frac{\infty}{\infty}$, $0 \times \infty$, $\infty - \infty$, $0 \times 0$, $1 \times \infty$ and $\infty \times 0$.

6. Sandwich's theorem

Miscellaneous examples:

Without L'H rule:

Key idea: The conjugate of trinomial $a+b-c$ is $a+b+c$, as one can see $[(a+b)-c][(a+b)+c] = (a+b)^2 - c^2$.

Special methods:
1. Stripping

Example:
$$\lim_{x \to 0} \frac{\sin(\sin(3x))}{\ln(1+\sin(\sin(5x)))} \\ \\ x \to 0, 3x \to 0, \sin(\sin(5x)) \to 0$$
We can "strip off" the outer sin in the numerator and $\ln (1+\_)$ in the denominator because the numerator is multiplicatively the same as $\sin (3x)$, whereas the denominator is multiplicatively the same as $\sin(\sin{5x})$.

Strip again, we have $$\lim_{x \to 0} \frac{\sin(3x)}{\sin(\sin(5x))} \\ \\ x \to 0, 3x \to 0, \sin(5x) \to 0$$
Finally, strip off the sines in both the numerator and the denominator.

$$\lim_{x \to 0} \frac{3x}{\sin(5x)}$$
Now it is clear the limit is $\frac{3}{5}$.

2. Approximations
$$\sin x \sim x, \tan x \sim x, \arctan x \sim x, \arcsin x \sim x \\ e^x - 1 \sim x \\ \ln(1+x) \sim x (for \: small \: x) \\ 1-\cos x \sim \frac{x^2}{2}, 1-\cos\sqrt x \sim \frac{x}{2}$$
Example 1:
$$\lim_{x \to 0} \frac{x-\sin x}{x^2 (e^x-1)} \stackrel{e^x - 1 \sim x}{=} \lim_{x \to 0} \frac{x-\sin x}{x^3} \stackrel{L'H}{=} \lim_{x \to 0} \frac {\frac{x^2}{2}}{3x^2} = \frac{1}{6}$$
Example 2:
$$\lim_{x \to 0} \frac{e^x - \sin x - 1}{1-\sqrt {1-x^2}} \stackrel{\sqrt {1-x^2} \sim 1 - \frac{x^2}{2}}{=} \lim_{x \to 0} \frac{e^x - \sin x - 1}{\frac{x^2}{2}} \\ \stackrel{L'H}{=} \lim_{x \to 0} \frac {e^x - \cos x}{x} \stackrel{L'H}{=} \lim_{x \to 0} (e^x + \sin x)=1$$
3. Taylor series expansion

Introduction

This is my math learning blog that focuses on anything about math, be it interesting applications, smart solutions, or enrichment knowledge.