# Cyclic expressions, fractions: Pre RMO, PRMO, IITJEE foundation 2019

In order to solve the following tutorial sheet, it helps to solve/understand and then apply the following beautiful cyclic relations or identities:

(Note if these look new to you, then you need to check the truth of all them; if all are v v familiar to you, just go ahead and crack the tutorial sheet below):

Core Identities in Cyclic Expressions:
1) $(b-c)+(c-a)+(a-b)=0$
2) $a(b-c)+b(c-a)+c(a-b)=0$
3) $a^{2}(b-c)+b^{2}(c-a)+c^{2}(a-b)=-(a-b)(b-c)(c-a)$
4) $bc(b-c)+ca(c-a)+ab(a-b)=-(a-b)(b-c)(c-a)$
5) $a(b^{2}-c^{2})+b(c^{2}-a^{2})+c(a^{2}-b^{2})=(a-b)(b-c)(c-a)$

Solve or simplify the following:

1) $\frac{a}{(a-b)(a-c)} + \frac{b}{(b-c)(b-a)} + \frac{c}{(c-a)(c-b)}$
2) $\frac{bc}{(a-b)(a-c)} + \frac{ca}{(b-c)(b-a)} + \frac{ab}{(c-a)(c-b)}$
3) $\frac{a^{2}}{(a-b)(a-c)} + \frac{b^{2}}{(b-c)(b-a)} + \frac{c^{2}}{(c-a)(c-b)}$
4) $\frac{a^{3}}{(a-b)(a-c)} + \frac{b^{3}}{(b-c)(b-a)} + \frac{c^{3}}{(c-a)(c-b)}$
5) $\frac{a(b+c)}{(a-b)(c-a)} + \frac{b(a+c)}{(a-b)(b-c)} + \frac{a(a+b)}{(c-a)(b-c)}$
6) $\frac{1}{a(a-b)(a-c)} + \frac{1}{b(b-c)(b-a)} + \frac{1}{c(c-a)(c-b)}$
7) $\frac{bc}{a(a^{2}-b^{2})(a^{2}-c^{2})} + \frac{ca}{b(b^{2}-c^{2})(b^{2}-a^{2})} + \frac{ab}{c(c^{2}-a^{2})(c^{2}-b^{2})}$
8) $\frac{(x-b)(x-c)}{(a-b)(a-c)} + \frac{(x-c)(x-a)}{(b-c)(b-a)} + \frac{(x-a)(x-b)}{(c-a)(c-b)}$
9) $\frac{bc(a+d)}{(a-b)(a-c)} + \frac{ca(b+d)}{(b-c)(b-a)} + \frac{ab(c+d)}{(c-a)(c-b)}$
10) $\frac{1}{(a-b)(a-c)(x-a)} + \frac{1}{(b-c)(b-a)(x-b)} + \frac{1}{(c-a)(c-b)(x-c)}$
11) $\frac{a^{2}}{(a-b)(a-c)(x+a)} + \frac{b^{2}}{(b-c)(b-a)(x+b)} + \frac{c^{2}}{(c-a)(c-b)(x+c)}$
12) $a^{2}\frac{(a+b)(a+c)}{(a-b)(a-c)} + b^{2}\frac{(b+c)(b+a)}{(b-c)(b-a)} + c^{2}\frac{(c+a)(c+b)}{(c-a)(c-b)}$
13) $\frac{a^{3}(b-c)+b^{3}(c-a)+c^{3}(a-b)}{(b-c)^{3}+(c-a)^{3}+(a-b)^{3}}$
14) $\frac{a^{2}(b-c)+b^{2}(c-a)+c^{2}(a-b)+2(c-a)(a-b)(b-c)}{(b-c)^{3}+(c-a)^{3}+(a-b)^{3}}$
15) $\frac{a^{3}(b-c)+b^{3}(c-a)+c^{3}(a-b)}{a^{2}(b-c)+b^{2}(c-a)+c^{2}(a-b)}$
16) $\frac{a^{2}(b-c)^{3}+b^{2}(c-a)^{3}+c^{2}(a-b)^{3}}{(a-b)(b-c)(c-a)}$
17) $\frac{\frac{b-c}{a} + \frac{c-a}{b} + \frac{a-b}{c}}{\frac{1}{a}(\frac{1}{b^{2}}-\frac{1}{c^{2}})+\frac{1}{b}(\frac{1}{c^{2}}-\frac{1}{a^{2}})+\frac{1}{c}(\frac{1}{a^{2}}-\frac{1}{b^{2}})}$^
18) $\frac{a^{2}(\frac{1}{a^{2}}-\frac{1}{b^{2}})+b^{2}(\frac{1}{a^{2}}-\frac{1}{c^{2}})+c^{2}(\frac{1}{b^{2}}-\frac{1}{a^{2}})}{\frac{1}{bc}(\frac{1}{c}-\frac{1}{b})+\frac{1}{ca}(\frac{1}{a}-\frac{1}{c})+\frac{1}{ab}(\frac{1}{b}-\frac{1}{c})}$
19) $\frac{a}{(a-b)(a-c)(x-a)} + \frac{b}{(b-c)(b-a)(x-b)} + \frac{c}{(c-a)(c-b)(x-c)}$

More later,
Nalin Pithwa

# A Primer: Generating Functions: Part II: for RMO/INMO 2019

We shall now complicate the situation a little bit. Let us ask for the combinations of the symbols $\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n}$ with repetitions of each symbol allowed once more in the combinations. For example, let there be only two symbols $\alpha_{1}, \alpha_{2}$. Let us look for combinations of the form:

$\alpha_{1}$, $\alpha_{2}$, $\alpha_{1}\alpha_{2}$, $\alpha_{1}\alpha_{1}$, $\alpha_{2}\alpha_{2}$, $\alpha_{1}\alpha_{1}\alpha_{2}$, $\alpha_{1}\alpha_{2}\alpha_{2}$, $\alpha_{1}\alpha_{1}\alpha_{2}\alpha_{2}$

where, in each combination, each symbol may occur once, twice, or not at all. The OGF for this can be constructed by reasoning as follows: the choices for $\alpha_{1}$ are not-$\alpha_{1}$, $\alpha_{1}$ once, $\alpha_{1}$ twice. This is represented by the factor $(1+\alpha_{1}t+\alpha_{1}^{2}t^{2})$. Similarly, the possible choices for $\alpha_{2}$ correspond to the factor $(1+\alpha_{2}t+\alpha_{2}^{2}t^{2})$. So, the required OGF is $(1+\alpha_{1}t+\alpha_{1}^{2}t)(1+\alpha_{2}t+\alpha_{2}^{2}t^{2})$

On expansion, this gives : $1+(\alpha_{1}+\alpha_{2})t+(\alpha_{1}\alpha_{2}+\alpha_{1}^{2}+\alpha_{2}^{2})t^{2}+(\alpha_{1}^{2}\alpha_{2}+\alpha_{1}\alpha_{2}^{2})t^{3}+(\alpha_{1}^{2}\alpha_{2}^{2})t^{4}$

Note that if we omit the term 1 (which corresponds to not choosing any $\alpha$), the other 8 terms correspond to the 8 different combinations listed in (*). Also, observe that the exponent r of the $t^{r}$ tells us that the coefficient of $t^{r}$ has the list or inventory of the r-combinations (under the required specification — in this case, with the restriction on repetitions of symbols) in it:

$\bf{Illustration}$

In the light of the foregoing discussion, let us now take up the following question again: in how many ways, can a total of 16 be obtained by rolling 4 dice once?; the contribution of each die to the total is either a “1” or a “2” or a “3” or a “4” or a “5” or a “6”. The contributions from each of the 4 dice have to be added to get the total — in this case, 16. So, if we write: $t^{1}+t^{2}+t^{3}+t^{4}+t^{5}+t^{6}$

as the factor corresponding to the first die, the factors corresponding to the other three dice are exactly the same. The product of these factors would be:

(*) $(t+t^{2}+t^{3}+t^{4}+t^{5}+t^{6})^{4}$

Each term in the expansion of this would be a power of t, and the exponent k of such a term $t^{k}$ is nothing but the total of the four contributions which went into it. The number of times a term $t^{k}$ can be obtained is exactly the number of times k can be obtained as a total on a throw of the four dice. So, if $\alpha_{k}$ is the coefficient of $t^{k}$ in the expansion, $\alpha_{16}$ is the answer for the above question. Further, since (*) simplifies to $(\frac{t(1-t^{6})}{1-t})^{4}$, it follows that the answer for the above question tallies with the coefficient specified in the following next question: calculate the coefficient of $t^{12}$ in $(\frac{(1-t^{6})}{(1-t)})^{4}$.6

Now, consider the following problem: Express the number $N(n,p)$ of ways of obtaining a total of n by rolling p dice, as a certain coefficient in a suitable product of binomial expansions in powers of t. [ this in turn, is related to the observation that the number of ways a total of 16 can be obtained by rolling 4 dice once is the same as the coefficient of $t^{12}$ in $(\frac{1-t^{6}}{1-t})^{4}$]:

So, we get that $N(n,p)=$ coefficient of $t^{n-p}$ in $(\frac{1-t^{6}}{1-t})^{p}$

Let us take an example from a graphical enumeration:

A $\it {graph}$ $G=G(V,F)$ is a set V of vertices a, b, c, …, together with a set $E=V \times V$ of $\it {edges}$ $(a,b), (a,a), (b,a), (c,b), \ldots$ If $(x,y)$ is considered the same as $(y,x)$, we say the graph is $\it{undirected}$. Otherwise, the graph is said to be $\it{directed}$, and we say ‘$(a,b)$ has a direction from a to b’. The edge $(x,x)$ is called a loop. The graph is said to be of order $|V|$.

If the edge-set E is allowed to be a multiset, that is, if an edge $(a,b)$ is allowed to occur more than once, (and, this may be called a ‘multiple edge’), we refer to the graph as a general graph.

If $\phi_{5}(n)$ and $\psi_{5}(n)$ denote the numbers of undirected (respectively, directed) loopless graphs of order 5, with n edges, none of them a multiple edge, find the series $\sum \phi_{5}(n)t^{n}$ and $\sum \psi_{5}(n)t^{n}$.

Applying our recently developed techniques to the above question, a graph of 5 specified vertices is uniquely determined once you specify which pairs of vertices are ‘joined’. Suppose we are required to consider only graphs with 4 edges. This would need four pairs of vertices to be selected out of the total of $5 \choose 2$ equal to 10 pairs that are available. So selection of pairs of vertices could be made in $10 \choose 4$ ways. Each such selection corresponds to one unique graph, with the selected pairs being considered as edges. More informally, having selected a certain pairs of vertices, imagine that the vertices are represented by dots in a diagram and join the vertices of each selected pair by a running line. Then, the “graph” becomes a “visible” object. Note that the number of graphs is just the number of selections of pairs of vertices. Hence, $\phi_{5}(4)=10 \choose 4$.

Or, one could approach this problem in a different way. Imagine that you have a complete graph on 5 vertices — the “completeness” here means that every possible pair of vertices has been joined by an edge. From the complete graph which has 10 edges, one has to choose 4 edges — any four, for that matter — in order to get a graph as required by the problem.

On the same lines for a directed graph, one has a universe of 10 by 2, that is, 29 edges to choose from, for, each pair x,y gives rise to two possible edges $(x,y)$ and $(y,x)$. Hence,

$\psi_{5}(4)=20 \choose 4$.

Thus, the counting series for labelled graphs on 5 vertices is $1 + \sum_{p=1}^{10} {10 \choose p}t^{p}$
and the counting series for directed labelled graphs on 5 vertices is
$1+ \sum_{p=1}^{20}{20 \choose p}t^{p}$.

Finally, the OGF for increasing words on an alphabet ${a,b,c,d,e}$ with $a is

$(1+at+a^{2}t^{2}+\ldots)(1+bt+b^{2}t^{2}+\ldots)(1+ct+c^{2}t^{2}+\ldots)\times (1+dt+d^{2}t^{2}+\ldots)(1+et+e^{2}t^{2}+\ldots)$

The corresponding OE is $(1+t+t^{2}+t^{3}+\ldots)^{5}$ which is nothing but $(1-t)^{-5}$ (this explains the following problem: Verify that the number of increasing words of length 10 out of the alphabet $\{a,b,c,d,e \}$ with $a is the coefficient of $t^{10}$ in $(1-t)^{-5}$ ).

We will continue this detailed discussion/exploration in the next article.

Until then aufwiedersehen,
Nalin Pithwa

# Functions — “s’wat” Math is about !! :-)

Reference: Nordic Mathematical Contest 1987, R. Todev:

Question:

Let f be a function, defined for natural numbers, that is strictly increasing, such that values of the function are also natural numbers and which satisfies the conditions $f(2)=a>2$ and $f(mn)=f(m)f(n)$ for all natural numbers m and n. Define the smallest possible value of a.

Solution:

Since, $f(n)=n^{2}$ is a function satisfying the conditions of the problem, the smallest possible a is at most 4. Assume that $a=3$. It is easy to prove by induction that $f(n^{k})={f(n)}^{k}$ for all $k \geq 1$. So, taking into account that f is strictly increasing, we get

${f(3)}^{4}=f(3^{4})=f(81)>f(64)=f(2^{6})={f(2)}^{6}=3^{6}=27^{2}>25^{2}=5^{4}$

as well as ${f(3)}^{8}=f(3^{8})=f(6561).

So, we arrive at $5. But, this is not possible, since $f(3)$ is an integer. So, $a=4$.

Cheers,

Nalin Pithwa.

# Algebra : max and min: RMO/INMO problem solving practice

Question 1:

If $x^{2}+y^{2}=c^{2}$, find the least value of $\frac{1}{x^{2}} + \frac{1}{y^{2}}$.

Solution 1:

Let $z^{'}=\frac{1}{x^{2}} + \frac{1}{y^{2}} = \frac{y^{2}+x^{2}}{x^{2}y^{2}} = \frac{c^{2}}{x^{2}y^{2}}$

$z^{'}$ will be minimum when $\frac{x^{2}y^{2}}{c^{2}}$ will be minimum.

Now, $let z=\frac{x^{2}y^{2}}{c^{2}}=\frac{1}{c^{2}}(x^{2})(y^{2})$….call this equation I.

Hence, z will be maximum when $x^{2}y^{2}$ is maximum but $(x^{2})(y^{2})$ is the product of two factors whose sum is $x^{2}+y^{2}=c^{2}$.

Hence, $x^{2}y^{2}$ will be maximum when both these factors are equal, that is, when

$\frac{x^{2}}{1}=\frac{y^{2}}{1}=\frac{x^{2}+y^{2}}{1}=\frac{c^{2}}{1}$. From equation I, maximum value of $z=\frac{c^{2}}{4}$. Hence, the least value of $\frac{1}{x^{2}} + \frac{1}{y^{2}}=\frac{4}{c^{2}}$.

Some basics related to maximum and minimum:

Basic 1:

Let a and b be two positive quantities, S their sum and P their product; then, from the identity:

$4ab=(a+b)^{2}-(a-b)^{2}$, we have

$4P=S^{2}-(a-b)^{2}$ and $S^{2}=4P+(a-b)^{2}$.

Hence, if S is given, P is greatest when $a=b$; and if P is given, S is least when $a=b$. That is,Ā if the sum of two positive quantities is given, their product is greatest when they are equal; and, if the product of two positive quantities is given, their sum is least when they are equal.

Basic 2:

To find the greatest value of a product the sum of whose factors is constant.

Solution 2:

Let there be n factors $a,b,c,\ldots, k$, and suppose that their sum is constant and equal to s.

Consider the product $abc\ldots k$, and suppose that a and b are any two unequal factors. If we replace the two unequal factors a and b by the two equal factors $\frac{a+b}{2}, \frac{a+b}{2}$, the product is increased, while the sum remains unaltered; hence,Ā so long as the product contains two unequal factors it can be increased without altering the sum of the factors;Ā therefore, the product is greatest when all the factors are equal. In this case, the value of each of the n factors is $\frac{s}{m}$, and the greatest value of the product is $(\frac{s}{n})^{n}$, or $(\frac{a+b+c+\ldots+k}{n})^{n}$.

Corollary to Basic 2:

If $a, b, c, \ldots k$ are unequal, $(\frac{a+b+c+\ldots+k}{n})^{2}>abc\ldots k$;

that is, $\frac{a+b+c+\ldots +k}{n} > (\frac{a+b+c+\ldots + k}{n})^{\frac{1}{n}}$.

By an extension of the meaning of the termsĀ arithmetic meanĀ andĀ geometric mean, this result is usually stated as follows:Ā the arithmetic mean of any number of positive quantities is greater than the geometric mean.

Basic 3:

To find the greatest value ofĀ $a^{m}b^{n}c^{p}\ldots$Ā whenĀ $a+b+c+\ldots$Ā is constant;Ā m,n, p, ….being positive integers.

Solution to Basic 3:

Since m,n,p, …are constants, the expression $a^{m}b^{n}c^{p}\ldots$ will be greatest when $(\frac{a}{m})^{m}(\frac{b}{n})^{n}(\frac{c}{p})^{p}\ldots$ is greatest. But, this last expression is the product of $m+n+p+\ldots$ factors whose sum is $m(\frac{a}{m})+n(\frac{b}{n})+p(\frac{c}{p})+\ldots$, or $a+b+c+\ldots$, and therefor constant. Hence, $a^{m}b^{n}c^{p}\ldots$ will be greatest when the factors $\frac{a}{m}, \frac{b}{n}, \frac{c}{p}, ldots$ are all equal, that is, when

$\frac{a}{m} = \frac{b}{n} = \frac{c}{p} = \ldots = \frac{a+b+c+\ldots}{m+n+p+\ldots}$

Thus, the greatest value is $m^{m}n^{n}p^{p}\ldots (\frac{a+b+c+\ldots}{m+n+p+\ldots})^{m+n+p+\ldots}$.

Some examples using the above techniques:

Example 1:

Show that $(1^{r}+2^{r}+3^{r}+\ldots+n^{r})>n^{n}(n!)^{r}$ where r is any real number.

Solution 1:

Since $\frac{1^{r}+2^{r}+3^{r}+\ldots+n^{r}}{n}>(1^{r}.2^{r}.3^{r}\ldots n^{r})^{\frac{1}{n}}$

Hence, $(\frac{1^{r}+2^{r}+3^{r}+\ldots+n^{r}}{n})^{n}>1^{r}.2^{r}.3^{r} \ldots n^{r}$

that is, $>(n!)^{r}$, which is the desired result.

Example 2:

Find the greatest value of $(a+x)^{3}(a-x)^{4}$ for any real value of x numerically less than a.

Solution 2:

The given expression is greatest when $(\frac{a+x}{3})^{3}(\frac{a-x}{4})^{4}$ is greatest; but, the sum of the factors of this expression is $3(\frac{a+x}{3})+4(\frac{a-x}{4})$, that is, $2a$; hence, $(a+x)^{3}(a-x)^{4}$ is greatest when $\frac{a+x}{3}=\frac{a-x}{4}$, that is, $x=-\frac{a}{7}$. Thus, the greatest value is $\frac{6^{3}8^{4}}{7^{7}}a^{r}$.

Some remarks/observations:

The determination ofĀ maximumĀ andĀ minimum values may often be more simply effected by the solution of a quadratic equation than by the foregoing methods. For example:

Question:

Divide an odd integer into two integral parts whose product is a maximum.

Let an odd integer be represented as $2n+1$; the two parts by x and $2n+1-x$; and the product by y; then $(2n+1)x-x^{2}=y$; hence,

$2x=(2n+1)\pm \sqrt{(2n+1)^{2}-4y}$

but the quantity under the radical sign must be positive, and therefore y cannot be greater than $\frac{1}{4}(2n+1)^{2}$, or, $n^{2}+n+\frac{1}{4}$; and since y is integral its greatest value must be $n^{2}+n$; in which case $x=n+1$, or n; thus, the two parts are n and $n+1$.

Sometimes we may use the following method:

Find the minimum value of $\frac{(a+x)(b+x)}{c+x}$.

Solution:

Put $c+x=y$; then the expression $=\frac{(a-c+y)(b-c+y)}{y}=\frac{(a-c)(b-c)}{y}+y+a-c+b-c$

which in turn equals

$(\frac{\sqrt{(a-c)(b-c)}}{\sqrt{y}}-\sqrt{y})^{2}+a-c+b-c+2\sqrt{(a-c)(b-c)}$.

Hence, the expression is a a minimum when the square term is zero; that is when $y=\sqrt{(a-c)(b-c)}$.

Thus, the minimum value is $a-c+b-c+2\sqrt{(a-c)(b-c)}$, and the corresponding value of x is $\sqrt{(a-c)(b-c)}-c$.

Problems for Practice:

1. Find the greatest value of x in order that $7x^{2}+11$ may be greater than $x^{3}+17x$.
2. Find the minimum value of $x^{2}-12x+40$, and the maximum value of $24x-8-9x^{2}$.
3. Show that $(n!)^{2}>n^{n}$ and $2.4.6.\ldots 2n<(n+1)^{n}$.
4. Find the maximum value of $(7-x)^{4}(2+x)^{5}$ when x lies between 7 and -2.
5. Find the minimum value of $\frac{(5+x)(2+x)}{1+x}$.

More later,

Nalin Pithwa.

# Algebra question: RMO/INMO problem-solving practice

Question:

If $\alpha$, $\beta$, $\gamma$ be the roots of the cubic equation $ax^{3}+3bx^{2}+3cx+d=0$. Prove that the equation in y whose roots are $\frac{\beta\gamma-\alpha^{2}}{\beta+\gamma-2\alpha} + \frac{\gamma\alpha-\beta^{2}}{\gamma+\\alpha-2\beta} + \frac{\alpha\beta-\gamma^{2}}{\alpha+\beta-2\gamma}$ is obtained by the transformation $axy+b(x+y)+c=0$. Hence, form the equation with above roots.

Solution:

Given that $\alpha$, $\beta$, $\gamma$ are the roots of the equation:

$ax^{3}+3bx^{2}+3cx+d=0$…call this equation I.

By relationships between roots and co-efficients, (Viete’s relations), we get

$\alpha+\beta+\gamma=-\frac{3b}{a}$ and $\alpha\beta+\beta\gamma+\gamma\alpha=\frac{3c}{a}$, and $\alpha\beta\gamma=-\frac{d}{a}$

Now, $\gamma=\frac{\beta\gamma-\alpha^{2}}{\beta+\gamma-2\alpha}=\frac{\frac{\alpha\beta\gamma}{\alpha}-\alpha^{2}}{(\alpha+\beta+\gamma)-3\alpha}=\frac{-\frac{d}{a\alpha}-\alpha^{2}}{-\frac{3b}{a}-3\alpha}=\frac{d+a\alpha^{3}}{3\alpha(b+a\alpha)}$, that is,

$3xy(b+ax)=d+ax^{3}$, or $ax^{3}-3ayx^{2}-3byx+d=0$…call this equation II.

Subtracting Equation II from Equation I, we get

$3(b+ay)x^{2}+3(c+by)x=0$

$(b+ay)x+c+by=0$ since $x \neq 0$

$axy+b(x+y)+c=0$ which is the required transformation.

Now, $(ay+b)x=-(by+c)$, that is, $x=-\frac{by+c}{ay+b}$

Putting this value of x in Equation I, we get

$-a(\frac{by+c}{ay+b})^{3}+3b(\frac{by+c}{ay+b})^{2}-3c(\frac{by+c}{ay+b})+d=0$, that is,

$a(by+c)^{3}-3b(by+c)^{2}(ay+b)+3c(by+c)(ay+b)^{2}-d(ay+b)^{3}=0$, which is the required equation.

Cheers,

Nalin Pithwa.

# Uses of mathematical induction to prove inequalities

Some classic examples are presented below to illustrate the use of mathematical induction to prove inequalities:

Example 1:

Prove the inequality $n<2^{n}$ for all positive integers n.

Proof 1:

Let $P(n)$ be the proposition that $n<2^{n}$.

Basis step:

$P(1)$ is true, because $1<2^{1}=2$. This completes the basis step.

Inductive step:

We first assume the inductive hypothesis that $P(k)$ is true for the positive integer k. That is, the inductive hypothesis $P(k)$ is the statement that $k<2^{k}$. To complete the inductive step, we need to show that if $P(k)$ is true, then $P(k+1)$, which is the statement that $k+1<2^{k+1}$ is also true. That is, we need to show that if $k<2^{k}$, then $k+1<2^{k+1}$. To show that this conditional statement is true for the positive integer k, we first add 1 to both sides of $k<2^{k}$ and then note that $1\leq 2^{k}$. This tells us that

$k+1<2^{k}+1 \leq 2^{k} + 2^{k} = 2.2^{k}=2^{k+1}$.

This shows that $P(k+1)$ is true; namely, that $k+1<2^{k+1}$, based on the assumption that $P(k)$ is true. The induction step is complete.

Therefore, because we have completed both the basis step and the inductive step, by the principle of mathematical induction we have shown that $n<2^{n}$ is true for all positive integers n. QED.

Example 2:

Prove that $2^{n} for every positive integer n with $n \geq 4$. (Note that this inequality is false for $n=1, 2, 3$).

Proof 2:

Let $P(n)$ be the proposition that $2^{n}

Basis Step:

To prove the inequality for $n \geq 4$ requires that the basis step be $P(4)$. Note that $P(4)$ is true because $2^{4} =16<24=4!$.

Inductive Step:

For the inductive step, we assume that $P(k)$ is true for the positive integer k with $k \geq 4$. That is, we assume that $2^{k} with $k \geq 4$. We must show that under this hypothesis, $P(k+1)$ is also also true. That is, we must show that if $2^{k} for the positive integer $k \geq 4$, then $2^{k+1}<(k+1)!$. We have

$2^{k+1}=2.2^{k}$ (by definition of exposition)

which $<2.k!$ (by the inductive hypothesis)

which $<(k+1).k!$ because $2

which equals $(k+1)!$ (by definition of factorial function).

This shows that $P(k+1)$ is true when $P(k)$ is true. This completes the inductive step of the proof.

We have completed the basis step and the inductive step. Hence, by mathematical induction $P(k)$ is true for all integers n with $n \geq 4$. That is, we have proved that $2^{n} is true for all integers n with $n \geq 4$. QED.

An important inequality for the sum of the reciprocals of a set of positive integers will be proved in the example below:

Example 3:

An inequality for Harmonic Numbers

The harmonic numbers $H_{j}, j=1,2,3, \ldots$ are defined by $H_{j}=1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{j}$.

For instance, $H_{4}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}=\frac{25}{12}$. Use mathematical induction to show that $H_{2*{n}} \geq 1 + \frac{n}{2}$, whenever n is a nonnegative integer.

Proof 3:

To carry out the proof, let $P(n)$ be the proposition that $H_{2^{n}} \geq 1 + \frac{n}{2}$.

Basis Step:

$P(0)$ is true because $H_{2^{0}}=H_{1}=1 \geq 1 + \frac{0}{2}$.

Inductive Step:

The inductive hypothesis is the statement that $P(1)$ is true, that is, $H_{2^{k}} \geq 1+\frac{k}{2}$, where k is a nonnegative integer. We must show that if $P(k)$ is true, then $P(k+1)$, which states that $H_{2^{k+1}} \geq 1 + \frac{k+1}{2}$, is also true. So, assuming the inductive hypothesis, it follows that

$H_{2^{k+1}}=1+\frac{1}{2}+\frac{1}{3}+\ldots +\frac{1}{2^{k}}+\frac{1}{2^{k}+1}+\ldots + \frac{1}{2^{k+1}}$ (by the definition of harmonic number)

which equals $H_{2^{n}}+\frac{1}{2^{k}+1} + \ldots + \frac{1}{2^{k+1}}$ (by the definition of the $2^{k}th$ harmonic number)

$\geq (1+\frac{k}{2})+\frac{1}{2^{k}+1}+\ldots + \frac{1}{2^{k+1}}$ (by the inductive hypothesis)

$\geq (1+\frac{k}{2}) + 2^{k}\frac{1}{2^{k+1}}$ (because there are $2^{k}$ terms each greater than or equal to $\frac{1}{2^{k+1}}$)

$\geq (1+\frac{k}{2})+\frac{1}{2}$ (canceling a common factor of $2^{k}$ in second term), which in turn, equals $1+ \frac{k+1}{2}$.

This establishes the inductive step of the proof.

We have completed the basis step and the inductive step. Thus, by mathematical induction $P(n)$ is true for all nonnegative integers. That is, the inequality $H_{2^{n}} \geq 1 + \frac{n}{2}$ for the harmonic number is valid for all non-negative integers n. QED.

Remark:

The inequality established here shows that theĀ harmonic series $1+\frac{1}{2}+\frac{1}{3}+\ldots \frac{1}{n}+\ldots$ is a divergent infinite series. This is an important example in the study of infinite series.

More later,

Nalin Pithwa

Reference: Discrete Mathematics and its Applications by Kenneth H. Rosen, Seventh Edition.