The Pigeonhole Principle

If there are more pigeons than pigeonholes and every pigeon goes into a pigeonhole, then some pigeon hole must have more than one pigeon in it. This is called the Pigeonhole Principle. We now wan to describe it mathematically. To do so, we need to define some notions such as sets and functions. A set is an unordered collection of objects without duplicates. Given a set $A$ we write that an object $a$ is an element of $A$ (or $a$ belongs to $A$) as $a\in A$, and that $a$ is not an element of $A$ as $a\notin A$. A function from one set to another is a rule that associates each member of the first set with exactly one member of the second set. If $f$ is a function from a set $X$ to another set $Y$ (denoted by $f:X\longrightarrow Y$) and $x\in X$, then $f(x)$ is the member of $Y$ that $f$ associates with $x$. We refer to $x$ as the argument of $f$ and $f(x)$ as the value of $f$ on that argument.

Example. Let $P=\{\mbox{Annie, Ben, Charlie, David, Evely, Franz, Greg, Marie}\}$ and $D=\{\mbox{Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}\}$. $b:P\longrightarrow D$ is the function that associates each of the eight people with the day of the week on which he or she was born. If Marie was born on Wednesday, then $b(\mbox{Marie})=\mbox{Wednesday}$.

A function $f: X\longrightarrow Y$ is also called a mapping or a map from $X$ to $Y$, and $f$ is said to map an element $x\in X$ to the element $f(x)\in Y$.

Now we are ready to describe the Pigeonhole Principle mathematically. Let $f: X\longrightarrow Y$ be a function from (a finite set) $X$ to (a finite set) $Y$. If $|X|>|Y|$ ($|X|$ is the number of elements of $X$), then there are elements $x_1,x_2\in X$ such that $x_1\ne x_2$ and $f(x_2)=f(x_2)$.

More generally we have the following Extended Pigeonhole Principle.

Theorem. For any finite sets $X$ and $Y$ and any positive integer $k$ such that $|X|>k|Y|$, if $f: X\longrightarrow Y$, then there are at least $k+1$ distinct members $x_1,\cdots,x_{k+1}\in X$ such that $f(x_1)=f(x_2)=\cdots=f(x_{k+1})$.

An integer $p$ divides another integer $q$, we write it as $p|q$, if $q=pk$ for some integer $k$. ($3|6$ because $6=2\cdot 3$.) We write $p\not|q$ if $p$ does note divide $q$. For example, $3\not|7$. If $x$ is a real number, we write $\lfloor x\rfloor$ for the greatest integer less than or equal to $x$. $\lfloor x\rfloor$ is called the floor of $x$. For example, $\left\lfloor\frac{17}{3}\right\rfloor=5$. $\lceil x\rceil$ is the smallest integer greater than or equal to $x$. $\lceil x\rceil$ is called the ceiling of $x$. $\lceil 3.7\rceil=4$.

Theorem. (Extended Pigeonhole Principle, Alternate version) Let $X$ and $Y$ be finite sets and let $f: X\longrightarrow Y$. Then there exists $y\in Y$ such that $f(x)=y$ for at least $\left\lceil\frac{|X|}{|Y|}\right\rceil$ values of $x$.

Proof. Let $m=|X|$ and $n=|Y|$. If $n|m$ then this is the Extended Pigeonhole Principle with $k=\frac{m}{n}-1=\left\lceil\frac{m}{n}\right\rceil-1$. If $n\not|m$, then again this is the Extended Pigeonhole Principle with $k=\left\lceil\frac{m}{n}\right\rceil-1$ since that is the largest integer less than $\frac{|X|}{|Y|}$.

If $p|q$ then $p$ is said to be a factor or a divisor of $q$. A prime number is an integer greater than 1 that is divisible only by itself and 1. For example, 7 is prime but 6 is not because $6=2\cdot 3$.

Theorem. (The Fundamental Theorem of Arithmetic) There is one and only one way to express a positive integer as a product of distinct prime numbers in increasing order and with positive integer exponents.

The prime decomposition (or prime factorization) of $n$ is $$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$$ where $p_1<p_2<\cdots<p_k$, all the $p_i$ are prime and the $e_i$ are positive integer exponents.

Example. $180=2^2\cdot 3^2\cdot 5^1$.

Theorem. If $m,n$ are integers greater than 1 that are relatively prime (we write $(m,n)=1$), $p$ is prime and $p|m\cdot n$, then either $p|m$ or $p|n$.

Proof. By Fundamental Theorem of Arithmetic there is one and only one way to write $m\cdot n$ as $$m\cdot n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$$ where the $p_i$ are prime. Since $p|m\cdot n$, $p$ must be one of the $p_i$, and each $p_i$ must appear in the unique prime decomposition of either $m$ or $n$. This completes the proof.

Remark. The condition $(m,n)=1$ is crucial for the above theorem to hold. Without it the statement is not necessarily true. For example, let $m=6$ and $n=9$. Then $(m,n)=3\ne 1$. 3 is prime and $3|m\cdot n=2^1\cdot 3^3$ but $3|m$ and $3|n$.

Theorem. There are arbitrary large prime numbers.

Proof. Pick some value of $k$ for which we know there are at least $k$ primes. (Since $p_1=2$, $p_2=3$, $p_3=5$, we could for example take $k=3$.) Let $P_1,\cdots,p_k$ be the first $k$ primes in increasing order. We now show how to find a prime number greater than $p_k$. This proces can be repeated indefinitely so there must be infinitely many primes. Let $N=p_1p_2\cdots p_k+1$. Then $N$ has no prime divisor less than or equal to $p_k$. Then either $N$ is not prime but has a prime factor greater than $p_k$ or $N$ is prime itself. This completes the proof.

Example. In $k=3$ case, $N=2\cdot 3\cdot 5+1=31$ itself is prime.

Example. Choose $m$ distinct numbers between $2$ and $40$ inclusive where $m\geq 13$. Then at least two of the numbers have some common divisor greater than 1.

Solution. There are 12 prime numbers between 2 and 40 inclusive. They are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Let $P$ be the set of these 12 prime numbers. Consider a set $X$ of 13 distinct numbers between 2 and 40 inclusive. Define $f: X\longrightarrow P$ by $f(x)=\mbox{the smallest prime that divides}\ x$. For example, $f(16)=2$, $f(17)=17$, $f(21)=3$. By the Pigeonhole Principle, since $31>12$, for at least two distinct members of $X$, the values of $f$ must be equal. Therefore, at least two members of $x$ have a common (prime) divisor (so obviously is greater than 1).

References.

[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019

Optimization Problems

In mathematics and also in applications, we often encounter problems that require to maximize or minimize the value of a certain quantity. The general procedure can be summarized as:

  1. Express the quantity to be maximized or minimized in terms of a single variable. The quantity may be described in terms of two variables however with given constraint it could be reduced to a single variable.
  2. Differentiate the function obtained in step 1 and set the derivative equal to 0.
  3. Solve the equation from step 2 to obtain critical values and determine whether they maximize or minimize the given quantity. Usually the first or second derivative test is a convenient tool for the required inspection.

Example. A farmer has 2400 ft of fencing and wants to fence off a rectangular field that borders a straight river. He needs no fence along the river. What are the dimensions of the field that has the largest area?

Solution. Let $x$ and $y$ denote the length and the width of the rectangular field. Suppose that the side along the river has the length $x$. Then the area is $A=xy$ and the required fencing in terms $x$ and $y$ is $x+2y=2400$. This fencing is a constraint and solve it for $y$ to obtain $y=1200-\frac{x}{2}$. Plugging this into $A$ for $y$, the area can be written as a function of a single variable $x$: $$A(x)=1200x-\frac{x^2}{2}$$ $A'(x)=1200-x$ and setting this equal to 0, we find $x=1200$. Since $A^{\prime\prime}(x)=-1<0$, by the second derivative test $x=1200$ gives rise to the absolute maximum of $A(x)$. The required dimensions are $1200\ \mbox{ft}\times 600\ \mbox{ft}$ where the side that borders the river is 1200 ft and the resulting largest area is 720,000 $\mbox{ft}^2$.

Example. A box with a square base and open top must have a volume of 32,000 $\mbox{cm}^3$. Find the dimensions of the box that minimize the amount of material used.

Solution. Let $x$ and $h$ be the length and the height of the box, respectively. Then $x^2h=32000$ and we want to minimize the surface area $A=x^2+4xh$. Solve the volume constraint for $h$ to obtain $h=\frac{32000}{x^2}$. Plugging this into $A$ for $h$, we write $A$ as a function of a single variable $x$: $$A(x)=x^2+\frac{128000}{x}$$ $A'(x)=2x-\frac{128000}{x^2}$ and setting it equalto 0, we find $x=40$. Since $A^{\prime\prime}(x)=2+\frac{256000}{x^3}>0$ for all $x>0$, $A(40)$ is the absolute minimum. Therefore the required dimensions are $40\ \mbox{cm}\times 40\ \mbox{cm}\times 20\ \mbox{cm}$.

Example. If 1200 $\mbox{cm}^2$ of material is available to make a box with a square base and an open top, find the largest possible volume of the box.

Solution. Let $x$ and $h$ be the length and the height of the box, respectively. Then $x^2+4xh=1200$ and we want to maximize $V=x^2h$. Solve the area for $h$ to obtain $h=\frac{1200-x^2}{4x}$. Plugging this into $V$, we write the volume as a function of a single variable $x$: $$V(x)=300x-\frac{1}{4}x^3$$ $V'(x)=300-\frac{3}{4}x^2$ and setting it equal to 0, we find $x=20$. Since $V'(x)$ is a quadratic polynomial with a negative leading coefficient, $V(20)=4000\ \mbox{cm}^3$ is the largest possible volume of the box.

Example. Find the point on the parabola $y^2=2x$ that is the closest to the point $(1,4)$.

Solution. Let $(x,y)$ denote a point on the parabola $y^2=2x$. The distance between $(x,y)$ and $(1,4)$ is $d=\sqrt{(x-1)^2+(y-4)^2}$ and we want to minimize this. Note minimizing $d$ is equivalent to minimizing $d^2=(x-1)^2+(y-4)^2$. Solve the equation of parabola for $x$ to obtain $x=\frac{y^2}{2}$. Plugging this into $d^2$, we can write it as a function of a single variable $y$: $$f(y)=\left(\frac{y^2}{2}-1\right)^2+(y-4)^2=\frac{y^4}{4}-8y+17$$ $f'(y)=y^3-8$ and setting it equal to 0, we find $y=2$. Since $f^{\prime\prime}(y)=3y^2>0$ for all $y\ne 0$, $(x,y)=(2,2)$ is the point on the parabola $y^2=2x$ that is the closest to $(1,4)$.

The shortest distance from (1,4) to the parabola y^2=2x.

Remark. The above problem also can be solved using a simple geometric fact that the shortest path from $(1,4)$ to the parabola $y^2=2x$ would be normal to the tangent line (i.e. the path is perpendicular to the tangent line). Let $(a,b)$ be the point on the parabola that is closest to $(1,4)$. By implicit differentiation we find $\frac{dy}{dx}=\frac{1}{y}$ and so the normal line at $(a,b)$ has the slope $-b$. The equation of the normal line is then $y-4=-b(x-1)$. Since this line is passing through $(a,b)$, $b-a=-b(a-1)$ or $ab=4$. $(a,b)$ is also on the parabola so we have $b^2=2a$. Solve the two equations simultaneously to obtain $b=2$ and hence $a=2$. Therefore, $(a,b)=(2,2)$.

Example. An open box is to be made out of a 6-inch by 18-inch piece of cardboard by cutting out squares of equal size from the four corners and bending up the sides. Find the dimensions of the resulting box that has the largest volume.

Solution. When you tackle this type of problems, it is very important to draw a picture that properly depicts the description of the problem as shown in the following figure.

From the figure, the length and the width of the box are, respectively, $18-2x$ and $y=6-2x$. Thus, the volume $V$ is $$V(x)=(6-2x)(18-2x)x=4x^3-48x^2+108x$$ To find the critical points, set $$V'(x)=12x^2-96x+108=0$$ or equivalently $x^2-8x+9=0$. This quadratic equation has two solutions $x=4\pm\sqrt{7}$. Recall that in order for a critical point $c$ to maximize the volume, it is required that $$V^{\prime\prime}(c)=24c-96<0,$$ i.e. $c<4$. Thus, $x=4-\sqrt{7}=1.35425$ maximizes the volume $V(x)$. The dimensions of the box that has the largest volume is then $$15.2915\times 3.2915$$

Example. A fence 4 feet tall runs parallel to a tall building at a distance of 2 feet from the building. What is the length of the shortest ladder that will reach from the ground over the fence to the wall of the building?

Solution. The following figure depicts the description of the problem.

The big and small right triangles are similar triangles, so we have $$\frac{x+2}{y}=\frac{x}{\sqrt{x^2+16}}$$ which is equal to $\cos\theta$. Solving the equation for $y$, we obtain $$y=\sqrt{x^2+16}+\frac{2\sqrt{x^2+16}}{x}$$ To minimize $y$, we find $$y’=\frac{x^3-32}{x^2\sqrt{x^2+16}}$$ and there is only one critical point $x=\root 3\of{32}=2\root 3\of{4}$. The resulting $y$ value, i.e. the length of the shortest ladder is then $8.32388$. By the second derivative, one can confirm that the critical point indeed minimizes the length of the ladder. But even without using the second derivative, one can make the length of such ladder as long as one likes, so there is no maximum length of such ladder.

Improper Integrals

When we defined the definite integral $\int_a^b f(x)dx$, it was assumed that the limits $a$ and $b$ of the integral are finite and the integrand $f(x)$ is continuous on the closed interval $[a,b]$. Even if these assumptions are not satisfied, we can still consider a notion of integral extended from the definite integral (the Riemann integral). This extended integral is called the improper integral.

Infinite Limits

A definite integral, in which one or both limits of integration are infinite, is defined by the following: \begin{align*}\int_a^\infty f(x)dx&=\lim_{t\to\infty}\int_a^tf(x)dx\\\int_{-\infty}^b f(x)dx&=\lim_{t\to -\infty}\int_t^bf(x)dx\end{align*} The improper integrals are said to be convergent if the corresponding limit exists. Otherwise, divergent.

If both $\int_{-\infty}^a f(x)dx$ and $\int_a^\infty f(x)dx$ are convergent, we define $$\int_{-\infty}^\infty f(x)dx=\int_{-\infty}^a f(x)dx+\int_a^\infty f(x)dx$$

Examples:

  1. $\int_{-\infty}^0e^xdx=\lim_{t\to -\infty}\int_t^0 e^xdx=\lim_{t\to -\infty}(1-e^t)=1$.
  2. $\int_2^\infty\frac{dx}{x}=\lim_{t\to \infty}\int_2^t\frac{dx}{x}=\lim_{t\to \infty}(\ln t-\ln 2)=\infty$.
  3. $\int_{-\infty}^0\frac{1}{1+x^2}dx=\lim_{t\to -\infty}\int_t^0\frac{1}{1+x^2}dx=\lim_{t\to -\infty}(-\tan^{-1}t)=\frac{\pi}{2}$.
  4. $\int_0^\infty\frac{1}{1+x^2}dx=\lim_{t\to\infty}\int_0^t\frac{1}{1+x^2}dx=\lim_{t\to\infty}(\tan^{-1}t)=\frac{\pi}{2}$.
  5. $\int_{-\infty}^\infty\frac{1}{1+x^2}dx=\int_{-\infty}^0\frac{1}{1+x^2}dx+\int_0^\infty\frac{1}{1+x^2}dx=\frac{\pi}{2}+\frac{\pi}{2}=\pi$.

Remarks:

  1. $\int_{-\infty}^\infty f(x)dx$ can be also defined by the double limit $$\int_{-\infty}^\infty f(x)dx=\lim_{b\to\infty\\a\to -\infty}\int_a^b f(x)dx$$
  2. $\int_{-\infty}^\infty\frac{2x}{1+x^2}dx$ is divergent as $\int_{-\infty}^0\frac{2x}{1+x^2}dx=-\infty$ and $\int_0^\infty\frac{2x}{1+x^2}dx=\infty$. On the other hand, $$\lim_{a\to\infty}\int_{-a}^a\frac{2x}{1+x^2}dx=0$$ This is called the Cauchy principal value of the integral $\int_{-\infty}^\infty\frac{2x}{1+x^2}dx$ and is denoted by $$\mathrm{p.v.}\int_{-\infty}^\infty\frac{2x}{1+x^2}dx$$ The Cauchy principal value is a method of assigning values to certain ill-defined improper integrals. We will not, however, be considering the Cauchy principal value here.

Discontinuous Integrand

If $f(x)$ is continuous for all values of $x$ in the domain $a\leq x\leq b$ except $x=b$ or $x=a$, $\int_a^b f(x)dx$ is defined by \begin{equation}\label{eq:impropint}\int_a^b f(x)dx=\lim_{t\to b-}\int_a^t f(x)dx\end{equation} or \begin{equation}\label{eq:impropint2}\int_a^b f(x)dx=\lim_{t\to a+}\int_t^b f(x)dx\end{equation} provided the corresponding limit exists.

Examples:

  1. $\int_{-1}^0\frac{dx}{x^2}=\lim_{t\to 0-}\left(-\frac{1}{t}-1\right)=\infty$.
  2. $\int_0^a\frac{dx}{\sqrt{a^2-x^2}}=\lim_{t\to a-}\left(\sin^{-1}\frac{t}{a}\right)=\frac{\pi}{2}$.

When $f(x)$ is continuous for all values of $x$ in the domain $a\leq x\leq b$ except $x=c$ (where $a< c <b$), $\int_a^b f(x)dx$ is defined by $$\int_a^b f(x)dx=\int_a^c f(x)dx+\int_c^b f(x)dx$$ where the integrals in the RHS are evaluated in accordance with \eqref{eq:impropint} and \eqref{eq:impropint2}, respectively.

Example. Consider $\int_{-1}^1\frac{dx}{x^2}$.

The graph of y=1/x^2 on [-1,1]

Solution. Since the integrand is discontinous at $x=0$, we write the integral in two parts as $$\int_{-1}^1\frac{dx}{x^2}=\int_{-1}^0\frac{dx}{x^2}+\int_0^1\frac{dx}{x^2}=\infty+\infty=\infty$$

Remarks. If one mindlessly evaluates the integral as an ordinary definite integral, we obtain $$\int_{-1}^1\frac{dx}{x^2}=\left[-\frac{1}{x}\right]_{-1}^1=-2$$ However, this is nonsense because the integrand is always positive.

Integration of Rational Functions by Partial Fractions

Let us consider the integral $\int\frac{5x-3}{x^2-2x-3}dx$. $\frac{d}{dx}(x^2-2x-3)=2x-2$ so substitution is not an option. Noting $x^2-2x-3=(x+1)(x-3)$, let us assume instead that $$\frac{5x-3}{x^2-2x-3}=\frac{A}{x+1}+\frac{B}{x-3}$$ Then \begin{align*}5x-3&=A(x-3)+B(x+1)\\&=(A+B)x-3A+B\end{align*} Hence we obtain a system of linear equations $$\left\{\begin{aligned}A+B&=5\\-3A+B&=-3\end{aligned}\right.$$ Solving this system simultaneously we find $A=2$ and $B=3$.

Alternation: Let’s begin with $5x-3=A(x-3)+B(x+1)$. For $x=3$, we get $12=4B$ so $B=3$. For $x=-1$, we get $-8=-4A$ so $A=2$. This method certainly has a computational advantage when it works over getting a system of linear equations and solving it.

Now \begin{align*}\int\frac{5x-3}{x^2-2x-3}dx&=2\int\frac{dx}{x+1}+3\int\frac{dx}{x-3}\\&=2\ln|x+1|+3\ln|x-3|+C\end{align*}

General method of writing a rational function $\frac{f(x)}{g(x)}$ as a sum of partial fractions

  1. Let $x-r$ be a linear factor of $g(x)$. Suppose that $(x-r)^m$ is the highest power of $x-r$ that divides $g(x)$ i.e. $x=r$ is a zero of $g(x)$ with multiplicity $m$. Then to this factor, assign the sum of the $m$ partial fractions $$\frac{A_1}{x-r}+\frac{A_2}{(x-r)^2}+\cdots+\frac{A_m}{(x-r)^m}$$
  2. Let $x^2+px+q$ be a quadratic factor of $g(x)$ that cannot be factored further into linear factors with real coefficients. Suppose that $(x^2+px+q)^n$ is the highest power of this factor that divides $g(x)$. Then to this factor assign the sum of the $n$ partial fractions $$\frac{B_1x+C_1}{x^2+px+q}+\frac{B_2x+C_2}{(x^2+px+q)^2}+\cdots+\frac{B_nx+C_n}{(x^2+px+q)^n}$$

Example. Evaluate $\int\frac{x^2+4x+1}{(x-1)(x+1)(x+3)}dx$.

Solution. Let $$\frac{x^2+4x+1}{(x-1)(x+1)(x+3)}=\frac{A}{x-1}+\frac{B}{x+1}+\frac{C}{x+3}$$ Then $$A(x+1)(x+3)+B(x-1)(x+3)+C(x-1)(x+1)$$ For $x=1$, $8A=6$ so $A=\frac{3}{4}$. For $x=-1$, $-4B=-2$ so $B=\frac{1}{2}$. For $x=-3$, $8C=-2$ so $C=-\frac{1}{4}$. Hence, \begin{align*}\int\frac{x^2+4x+1}{(x-1)(x+1)(x+3)}dx&=\frac{3}{4}\int\frac{dx}{x-1}+\frac{1}{2}\int\frac{dx}{x+1}-\frac{1}{4}\int\frac{dx}{x+3}\\&=\frac{3}{4}\ln|x-1|+\frac{1}{2}\ln|x+1|-\frac{1}{4}\ln|x+3|+C\end{align*}

Example. Evaluate $\int\frac{6x+7}{(x+2)^2}dx$.

Solution. Let $\frac{6x+7}{(x+2)^2}=\frac{A}{x+2}+\frac{B}{(x+2)^2}$. Then $A=6$ and $B=-5$. Hence, \begin{align*}\int\frac{6x+7}{(x+2)^2}dx\\&=6\int\frac{dx}{x+2}-5\int\frac{dx}{(x+2)^2}\\&=6\ln|x+2|+\frac{5}{x+2}+C\end{align*}

Example. [Integrating an Improper Fraction] Evaluate $\int\frac{2x^3-4x^2-x-3}{x^2-2x-3}dx$.

Solution. By long division, divide $2x^3-4x^2-x-3$ by $x^2-2x-3$ to obtain quotient $2x$ and remainder $5x-3$. Thus $2x^3-4x^2-x-3=(x^2-2x-3)\cdot 2x+5x-3$ and $$\frac{2x^3-4x^2-x-3}{x^2-2x-3}=2x+\frac{5x-3}{x^2-2x-3}$$ $\frac{5x-3}{x^2-2x-3}$ is a proper fraction so we can apply the above method to write it as $$\frac{5x-3}{x^2-2x-3}=\frac{3}{x-3}+\frac{2}{x+1}$$ Hence, \begin{align*}\int\frac{2x^3-4x^2-x-3}{x^2-2x-3}dx&=\int 2xdx+3\int\frac{dx}{x-3}+2\int\frac{dx}{x+1}\\&=x^2+3\ln|x-3|+2\ln|x+1|+C\end{align*}

Remark. Instead of writing $\frac{5x-3}{x^2-2x-3}$ as $\frac{A}{x-3}+\frac{B}{x+1}$, let $$5x-3=A(x+1)+B(x-3)$$ $\frac{5x-3}{x+1}=A+\frac{B(x-3)}{x+1}$ and if $x=3$, $A=3$. $\frac{5x-3}{x-3}=\frac{A(x+1)}{x-3}+B$ and if $x=-1$, $B=2$. This is called Heaviside’s method and is easier to determine coefficients than the standard method we discussed above. However it can be useful only when the denominator has all linear factors.

Example. Evaluate $\int\frac{-2x+4}{(x^2+1)(x-1)^2}dx$.

Solution. Let $$\frac{-2x+4}{(x^2+1)(x-1)^2}=\frac{Ax+B}{x^2+1}+\frac{C}{x-1}+\frac{D}{(x-1)^2}$$ Then we obtain \begin{align*}-2x+4&=(Ax+B)(x-1)^2+C(x-1)(x^2+1)+D(x^2+1)\\&=(A+C)x^3+(-2A+B-C+D)x^2+(A-2B+C)x+(B-C+D)\end{align*} and hence the equations $A+C=0$, $-2A+B-C+D=0$, $A-2B+C=-2$, and $B-C+D=4$. Solve these equations simultaneously to obtain $A=2$, $B=1$, $C=-2$, and $D=1$. Therefore, \begin{align*}\int\frac{-2x+4}{(x^2+1)(x-1)^2}dx&=\int\frac{2x+1}{x^2+1}dx-2\int\frac{dx}{x-1}+\int\frac{dx}{(x-1)^2}\\&=\int\frac{2x}{x^2+1}dx+\int\frac{1}{x^2+1}dx-2\int{dx}{x-1}+\int\frac{dx}{(x-1)^2}\\&=\ln(x^2+1)+\tan^{-1}x-2\ln|x-1|-\frac{1}{x-1}+C\end{align*}

Example. Evaluate $\int\frac{dx}{x(x^2+1)^2}$.

Solution. Let $$\frac{1}{x(x^2+1)^2}=\frac{A}{x}+\frac{Bx+C}{x^2+1}+\frac{Dx+E}{(x^2+1)^2}$$ Then we have \begin{align*}1&=A(x^2+1)^2+(Bx+C)x(x^2+1)+(Dx+E)x\\&=(A+B)x^4+Cx^3+(2A+B+D)x^2+(C+E)x+A\end{align*} and comparing the coefficients we obtain the equations $A+B=0$, $C=0$, $2A+B+D=0$, $C+E=0$, and $A=1$. Solve these equations simultaneously to obtain $A=1$, $B=-1$, $C=0$, $D=-1$, and $E=0$. Therefore, \begin{align*}\int\frac{dx}{x(x^2+1)^2}&=\int\frac{dx}{x}-\int\frac{x}{x^2+1}dx-\int\frac{x}{(x^2+1)^2}dx\\&=\ln|x|-\frac{1}{2}\ln(x^2+1)+\frac{1}{2(x^2+1)}+C\end{align*}

The Laplace Transform: Forced Vibration without Damping and Resonance

Forced Vibration without Damping

Let us consider forced harmonic oscillation without damping
$$m\ddot{X}(t)+kX(t)=F(t)$$
with initial conditions $X(0)=x_0$ and $\dot{X}(0)=v_0$. The transformed equation is
$$m[s^2x(s)-sx_0-v_0]+kx(s)=f(s)$$
from which we obtain
\begin{equation}\begin{aligned}
x(s)&=\frac{sx_0+v_0}{s^2+\omega_0^2}+\frac{1}{m}\frac{f(s)}{s^2+\omega_0^2}\\&=\frac{s}{s^2+\omega_0^2}x_0+\frac{v_0}{\omega_0}\frac{\omega_0}{s^2+\omega_0^2}+\frac{f(s)}{m\omega_0}\frac{\omega_0}{s^2+\omega_0^2}
\end{aligned}\label{eq:laplace18}\end{equation}
where $\omega_0=\sqrt{\frac{k}{m}}$. By taking the inverse transform of \eqref{eq:laplace18} we find the solution $X(t)$ as
\begin{equation} \begin{aligned}
X(s)&=x_0\cos\omega_0t+\frac{v_0}{\omega_0}\sin\omega_0t+\frac{1}{m\omega_0}F(t)\ast\cos\omega_0t\\
&=x_0\cos\omega_0t+\frac{v_0}{\omega_0}\sin\omega_0t+\frac{1}{m\omega_0}\int_0^t\sin\omega_0(t-\tau)F(\tau)d\tau \end{aligned}\label{eq:laplace19}\end{equation}

Resonance

Let $F(t)$ be the sinusoidal force $F(t)=F_0\sin\omega t$ where $F_0$ and $\omega$ are positive constants. Then
$$f(s)=\mathcal{L}{F(t)}=F_0\frac{\omega}{s^2+\omega^2}$$
and \eqref{eq:laplace18} can be written
$$x(s)=\frac{x_0s+v_0}{s^2+\omega_0^2}+\frac{F_0}{m}\frac{\omega}{(s^2+\omega_0^2)(s^2+\omega^2)}$$
If $\omega\ne\omega_0$, $\frac{1}{(s^2+\omega_0^2)(s^2+\omega^2)}=\frac{1}{\omega^2-\omega_0^2}\left[\frac{1}{s^2+\omega_0^2}-\frac{1}{s^2+\omega^2}\right]$ and
$$x(s)=\frac{s}{s^2+\omega_0^2}x_0+\frac{v_0}{\omega_0}\frac{\omega_0}{s^2+\omega_0^2}+\frac{F_0\omega}{m\omega_0(\omega^2-\omega_0^2)}\frac{\omega_0}{s^2+\omega_0^2}-\frac{F_0}{m(\omega^2-\omega_0^2)}\frac{\omega}{s^2+\omega^2}$$
Thus by taking the inverse transform we obtain $X(t)$
$$X(t)=x_0\cos\omega_0t+\frac{1}{\omega_0}\left[v_0+\frac{F_0\omega}{m(\omega^2-\omega_0^2)}\right]\sin\omega_0t-\frac{F_0}{m(\omega^2-\omega_0^2)}\sin\omega t$$
The motion is the superposition of two simple harmonic motions, one with frequency $\omega_0$ (the natural component of the vibration) and the other with frequency $\omega$ (the forced component of the vibration). The natural vibrations are not present if
$$x_0=0,\ v_0=\frac{F_0\omega}{m(\omega_0^2-\omega^2)}$$

When $\omega=\omega_0$,
\begin{align*}x(s)&=\frac{x_0s+v_0}{s^2+\omega_0^2}+\frac{F_0}{m}\frac{\omega_0}{(s^2+\omega_0^2)^2}\\&=\frac{s}{s^2+\omega_0^2}x_0+\frac{v_0}{\omega_0}\frac{\omega_0}{s^2+\omega_0^2}+\frac{F_0}{2m}\frac{1}{s}\frac{2\omega_0s}{s^2+\omega^2} \end{align*}
In the first example here, we found $\mathcal{L}^{-1}\left\{\frac{2\omega_0s}{(s^2+\omega_0^2)^2}\right\}=t\sin\omega_0t$. Using the formula here
\begin{align*} X(t)&=x_0\cos\omega_0t+\frac{v_0}{\omega_0}\sin\omega_0t+\frac{F_0}{2m}\int_0^t\tau\sin\omega_0\tau d\tau\\&=x_0\cos\omega_0t+\frac{1}{\omega_0^2}\left(v_0\omega_0+\frac{F_0}{2m}\right)\sin\omega_0t-\frac{F_0}{2m\omega_0}t\cos\omega_0t \end{align*}
In view of the last term, the amplitude of the oscillations increases indefinitely. In this case, the force $F(t)$ is said to be in resonance with the system.

Vibrations can be quite destructive. A striking example is the collapse of Tacoma Narrows Bridge in 1940. In my college mechanics class I was told that this was resulted from resonance. However the catastrophic vibrations were not actually due to simple mechanical resonance but to a complicated interaction between the bridge and the winds passing through it. Such a phenomenon is called flutter, which is a kind of self-oscillation.

The following is a footage of the old Tacoma Narrows Bridge collapsing: