Author Archives: Sung Lee I am a mathematician and a physics buff. I am interested in studying mathematics inspired by theoretical physics as well as theoretical physics itself. Besides, I am also interested in studying theoretical computer science.

Strong Induction

The Strong Principle of Mathematical induction

To prove that a predicate $P(n)$ holds for every number $n\geq n_0$,

Base Case. Prove $P(m)$ for all $m$ such that $n_0\leq m\leq n_1$.

Induction Hypothesis. Let $n\geq n_1$ be arbitrary but fixed, and assume that $P(m)$ holds whenever $n_0\leq m\leq n$.

Induction Step. Assuming the induction hypothesis, show that $P(n+1)$ holds.

Example. Consider the sequence $a_1=3$, $a_2=5$, and for all $n>2$, $a_n=3a_{n-1}-2a_{n-2}$. Prove by strong induction that $a_n=2^n+1$ for all integers $n\geq 1$.

Proof. Let $P(n)$ be the predicate $a_n=2^n+1$.

Base Case. \begin{align*}P(1): a_1=3=2^1+1\\P(2): a_2=5=2^2+1\end{align*}

Induction Hypothesis. Fix $n\geq 2$, and assume that for all $1\leq n\leq n$, $P(m)$ holds i.e. $a_m=2^m+1$.

Induction Step. Show $P(n+1)$ i.e. $a_{n+1}=2^{n+1}+1$ holds. \begin{align*}a_{n+1}&=3a_n-2a_{n-1}\\&=3(2^n+1)-2(2^{n-1}+1)\\&=2\cdot 2^n+1\\&=2^{n+1}+1\end{align*}

Well-Ordering Principle

Any nonempty set of nonnegative integers has a smallest element.

Well-Ordering Principle may appear to be unrelated to the Principle of Mathematical Induction, however the two are indeed equivalent to each other.

We now prove, with the aid of Well-Ordering Principle, the Fundamental Theorem of Arithmetic (every integer $n$ greater than 1 has a unique prime decomposition)

Proof. We prove by induction on $n$.

Base Case. $n_0=2=2^1$. We are done.

Induction Hypothesis. Fix $n\geq 2$, and suppose that we know that every $m$, $2\leq m\leq n$, has a unique prime decomposition (factorization).

Induction Step. We prove that the statement is true for $n+1$. If $n+1$ is a prime, we are done. Suppose that $n+1$ is not a prime. Let $S$ be the set of all its factors greater than 1. By Well-Ordering Principle, $S$ has the smallest element $p$, which must be prime. (otherwise $p$ wouldn’t be the smallest factor of $n+1$.) Let $q=\frac{n+1}{p}$. Then by induction hypothesis ($q\leq n$), $q$ has the unique prime decomposition $$q=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\ (p_1<p_2<\cdots<p_k)$$ Now $p$ is either $p_1$ or a smaller prime than $p_1$. If $p=p_1$ then $$n+1=p_1^{e_1+1}p_2^{e_2}\cdots p_k^{e_k}$$ If $p$ is a smaller prime than $p_1$, say $p_0$, then $$n+1=p_0^1p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$$ It’s easy to show that no number can have more than one prime decomposition. This is left as an exercise for readers.

References.

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

Proof by Mathematical Induction

The Principle of Mathematical Induction

To prove that a predicate $P(n)$ is true for all $n\geq n_0$:

Base Case. Prove that the predicate $P(n)$ holds for a particular value $n_0$.

Induction Hypothesis. Suppose that $P(n)$ holds for some fixed value $n\geq n_0$.

Induction Step. Prove that if the induction hypothesis is true then $P(n+1)$ holds as well.

Example. Prove that for any $n\geq 1$, \begin{align*}\sum_{i=0}^{n-1}2^i&=1+2+2^2+2^3+\cdots+2^{n-1}\\&=2^n-1\end{align*}

Proof. $P(n)$: $\sum_{i=1}^{n-1}2^i=2^n-1$.

Base Case. $P(1)$: $n_0=$. $\sum_{i=0}^02^i=2^1-1$. $P(1)$ is true since the LHS=the RHS=1.

Induction Hypothesis. Suppose that $P(n)$ is true for a fixed $n\geq 1$ that is, $$\sum_{i=1}^{n-1}2^i=2^n-1$$

Induction Step. Show that $P(n+1)$ is true. \begin{align*}\sum_{i=1}^n2^i&=\sum_{i=1}^{n-1}2^i+2^n\\&=2^n-1+2^n\\&=2\cdot 2^n-1\\&=2^{n+1}-1\end{align*} Therefore $P(n+1)$ is true.

Example. Prove that for any $n\geq 1$, $$\sum_{i=1}^ni=\frac{n(n+1)}{2}$$

Proof. P(n):=\sum_{i=1}^ni=\frac{n(n+1)}{2}Base Case. n_0=1. P(1)=\sum_{i=1}^1i=\frac{1(1+1)}{2} is true. Induction Hypothesis. Suppose that P(n) is true for some fixed n\geq 1. Induction Step. Show that P(n+1) is true. \begin{align*}\sum_{i=1}^{n+1}i&=\sum_{i=1}^ni+n+1\\&=\frac{n(n+1)}{2}+n+1\\&=\frac{(n+1)(n+2)}{2}\end{align*} Therefore P(n+1) is true. Example. Prove that for any n\geq 1,\prod_{i=1}^n\left(1+\frac{1}{i}\right)=\left(1+\frac{1}{1}\right)\cdot\left(1+\frac{1}{2}\right)\cdots\left(1+\frac{1}{n}\right)=n+1Proof. P(n): \prod_{i=1}^n\left(1+\frac{1}{i}\right)=n+1. Base Case. n_0=1. P(1): \prod_{i=1}^1\left(1+\frac{1}{i}\right)=1+1 is true. Induction Hypothesis. Suppose that P(n) is true for some fixed n\geq 1. Induction Step. Show that P(n+1) is true. \begin{align*}\prod_{i=1}^{n+1}\left(1+\frac{1}{i}\right)&=\prod_{i=1}^n\left(1+\frac{1}{i}\right)\cdot\left(1+\frac{1}{n+1}\right)\\&=(n+1)\cdot\left(1+\frac{1}{n+1}\right)\\&=n+1+1=n+2\end{align*} Therefore P(n+1) is true as well. In computer science, 0 and 1 are called the two bits. A sequence of bits, such as 100001001, is called a binary string, bit string or string of bits. For example, 10001001 is a bit string of length 8. The compliment of a bit string is the result of replacing all the 0s by 1s and vice versa. For example, the compliment of 10001001 is 01110110. The concatenation of two bit strings is the result of writing one after another. For example, the concatenation of 10001001 and 111 is 10001001111. Let us define a sequence of bit strings as follows: \begin{align*}T_0&=0\ \mbox{and for any}\ n\geq 0\\T_{n+1}&=\mbox{the concatenation of}\ T_n\ \mbox{and the compliment of}\ T_n\end{align*} This is an example if an inductive definition or a recursive definition. The resulting sequence is called Thue sequence named after a Norwegian mathematician Axel Thue. The first few terms of the Thue sequence are: \begin{align*}T_0&=0\\T_1&=01\\T_2&=0110\\T_3&=01101001\\T_4&=0110100110010110\end{align*} Example. Prove that for any n\geq 0, the length of T_n is 2^n. Proof. We prove this by induction. Base Case. T_0 has length 1=2^0. Induction Hypothesis. Assume that T_n has length 2^n for some fixed n\geq 0. Induction Step. T_{n+1} is the result of concatenating T_n with its compliment, so its length is2^n+2^n=2\cdot2^n=2^{n+1}Example. Prove that for every n\geq 1, T_n begins with 01, and ends with 01 if n is odd or with 10 if n is even. Proof. Base Case. T_1=01 so the statement is true. Induction Hypothesis. Suppose that for some fixed n\geq 1, T_n ends with 01 if n is odd or 10 if n is even. Induction Step. T_{n+1} ends with the compliment of the last two bits of T_n. n+1 is even if n is odd and it is odd if n is even. So T_{n+1} ends with 01 if n+1 is odd or 10 if n+1 is even. Example. Prove that for every n\geq 0, T_n never has more than two 0s or two 1s in a row. Proof. T_0 has only one bit, so the statement is true for T_0. We prove the statement by induction starting from n_0=1. Base Case. T_1=01 has no more than two identical bits in a row. Induction Hypothesis. Assume that T_n has no more than two 0s or two 1s in a row. Induction Step. T_{n+1} includes T_n in the first half and its compliment in the second half. By induction hypothesis, neither has more than two 0s nor two 1s in a row. Due to the statement in the previous example, the four bits at the junction can be either 0110 (if n is odd) or 1010 (if n is even). Neither of them contains more than two 0s or two 1s in a row. This completes the proof. Mathematical induction also can be used to prove the Pigeonhole Principle. Example. Prove that if f:X\longrightarrow Y and |X|>|Y|, then there exists x_1, x_2\in X with x_1\ne x_2 such that f(x_1)=f(x_2). Proof. We prove the statement by induction on the size of the set X. Let f: X\longrightarrow Y be a function and |X|>|Y|. Base Case. n_0=2. If |X|=2 and |X|>|Y|, then |Y|=1 and the two elements in X map to the unique element of Y. Induction Hypothesis. Let |X|=n for some fixed n\geq 2 and assume that the statement is true i.e., there exist x_,x_2\in X with x_1\ne x_2 such that f(x_1)=f(x_2). Induction Step. Let |X|=n+1. Pick an element x\in X. If there exists x’\in X with x’\ne x such that f(x)=f(x’), then we are done. Suppose not. Then f: X\setminus\{x\}\longrightarrow Y\setminus\{f(x)\}, |X\setminus\{x\}|=n and |X\setminus\{x\}|>|Y\setminus\{f(x)\}|. By induction hypothesis, there exist x_1,x_2\in X\setminus\{x\} with x_1\ne x_2 such that f(x_1)=f(x_2). This completes the proof. References.  Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019 Basic Proof Techniques Theorem. Every odd integer is equal to the difference between the square of two integers. For example, \begin{align*}1&=1^2-0^2\\3&=4-1=2^2-1^1\\5&=9-4=3^2-2^2\\7&=16-9=4^2-3^2\end{align*} Note that an arbitrary odd integer can be written as 2k+1 for some integer k. The above examples can be written as \begin{align*}1&=2\cdot 0+1=(0+1)^2-0^2\\3&=2\cdot 1+1=(1+1)^2-1^2\\5&=2\cdot 2+1=(2+1)^2-2^2\\7&=2\cdot 3+1=(3+1)^2-3^2\end{align*} Based on this observation we may conjecture that2k+1=(k+1)^2-k^2$$for all nonnegative integer k. Proving this conjecture is equivalent to proving the above theorem. This can be shown straightforwardly.$$(k+1)^2-k^2=k^2+2k+1-k^2=2k+1Theorem. For any integer n, n^2 is odd if and only if n is odd. In the statement you see the conjunction if and only if. The statement is actually the following two statements in one: 1. n^2 is odd if n is odd. 2. n^2 is odd only if n is odd. The statement 1 means that if n is odd then n^2 is odd. The statement 2 means that if n^2 is odd then n is odd. Proof. (Only if) We prove this by contradiction. (This is an indirect proof.) Suppose that there exists an integer n such that n^2 is odd but n is not. Then n is even so n=2k for some integer k. However n^2=(2k)^2=4k^2 is even so this is a contradiction. Therefore, there is no integer n such that n^2 is odd but n is even. (If) Suppose that n is odd. Then n=2k+1 for some integer k. \begin{align*}n^2=(2k+1)^2&=4k^2+4k+1\\&=2(2k^2+2k)+1\end{align*} is odd. (This is a direct proof.) Corollary. If n is odd, then n^4 is odd. Proof. Since n is odd, by the theorem n^2 is odd, and again by the theorem n^4 is odd. “If p then q” is logically equivalent to “If not q then not p.” “If p then q” and “If not q then not p” are contrapositives of each other. Example. The statements “If n^2 is odd then n is odd and “If n is not odd (i.e. n is even) then n^2 is not odd (i.e. n^2 is even)” are contrapositives of each other, and they are logically equivalent statements. Here is another example of proof by contradiction. Theorem. \sqrt{2} is irrational. Proof. Suppose that sqrt{2} is rational Then \sqrt{2}=\frac{a}{b} for some integer a and b\ne=0. Without loss of generality we may also assume that at most one of a and b is even. Multiplying \sqrt{2}=\frac{a}{b} by b, we get \sqrt{2}b=a. Squaring this we get 2b^2=a^2 \Longrightarrow a^2 is even and this means a is even by the previous theorem. So, a can be written as a=2k. Now, 2b^2=(2k)^2=4k^2 \Longrightarrow b^2=2k^2 \Longrightarrow b^2 is even and by the previous theorem b is even. A contradiction! Therefore, \sqrt{2} is irrational. References.  Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019 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 isn=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.  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(2)=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+17f'(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)$.