Tag: Induction

Prove that if n real numbers have product 1, then they have sum greater than n

by RoRi

July 10, 2015

Given $a_1, \ldots, a_n \in \mathbb{R}_{>0}$ . Then if

$\prod_{k=1}^n a_k = 1,$

prove that

$\sum_{k=1}^n a_k \geq n$

with equality if and only if $a_1 = \cdots = a_n = 1$ .

Proof. We consider two cases: the first one is the case that $a_1 = \cdots = a_n = 1$ , and the second is the case that $a_k \neq 1$ for at least one $k$ in $1, \ldots, n$ .
Case #1: If $a_1 = \cdots = a_n = 1$ , then

$\prod_{k=1}^n a_n = \prod_{k=1}^n 1 = 1 \qquad \text{and} \qquad \sum_{k=1}^n a_k = \sum_{k=1}^n 1 = n.$

Thus, the inequality holds (in fact, equality holds).
Case #2: Now for the case that at least one of the $a_k \neq 1$ . The proof is by induction on the number of terms $n$ . For the case $n=2$ , we have $a_1 \cdot a_2 = 1$ , and by assumption at least one of these is not equal to 1. But, if one of them is not 1, then neither is the other (since the product must equal 1). So,

$\begin{align*} a_1 \cdot a_2 = 1 &&\implies \ a_2 &= \frac{1}{a_1} \\ &&\implies \ a_1 + a_2 &= a_1 + \frac{1}{a_1} \\ &&\implies &= \frac{a_1^2 + 1}{a_1} \\ &&\implies &= \frac{a_1^2 - 2a_1 + 1 + 2a_1}{a_1} \\ &&\implies &= \frac{(a_1 - 1)^2}{a_1} + 2 \\ &&\implies &> 2. \end{align*}$

Where the final inequality follows since $\frac{(a_1 - 1)^2}{a_1} > 0$ since $a_1 > 0$ by assumption. Therefore, the inequality indeed holds for the case $n=2$ .
Assume then that the inequality holds for some $n = k \in \mathbb{Z}_{>0}$ . Then, let $a_1, \ldots, a_{k+1} \in \mathbb{R}_{>0}$ with $a_i \neq 1$ for at least one $i = 1, \ldots, k+1$ . If $a_i < 1$ , then there must be some $j \neq i$ such that $a_j > 1$ (otherwise, if $a_j \leq 1$ for all $j \neq i$ , then $a_1 \cdot \cdots \cdot a_{k+1} < 1$ ). Similarly, if $a_i > 1$ , then there is some $j \neq i$ such that $a_j < 1$ . Hence, we have a pair, $a_i, a_j$ with one member of the pair greater than 1, and the other less than 1. Without loss of generality (since multiplication and addition are commutative), let this pair be $a_1$ and $a_{k+1}$ . Then, define $b = a_1 \cdot a_{k+1}$ . So,

$\underbrace{b \cdot a_2 \cdot \cdots \cdot a_k}_{k\text{-elements}} = 1 \quad \implies \quad b_1 + a_2 + \cdots + a_k \geq k. \qquad \qquad (\text{Ind. hyp.})$

Further, since $(1-a_1)(1-a_{k+1}) < 0$ (since one of $a_1, a_{k+1}$ is greater than 1 and the other is less than 1, so one of $(1-a_1), (1-a_{k+1})$ is positive and the other is negative), we have

$1 - a_1 - a_{k+1} + a_1 a_{k+1} < 0 \quad \implies \quad b < a_1 + a_{k+1} - 1.$

Thus,

$b + a_2 + \cdots + a_k \geq k \quad \implies \quad a_1 + a_2 + \cdots + a_k + a_{k+1} \geq k+1.$

Hence, the inequality holds for $k+1$ ; and therefore, for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$

Prove an inequality for the nth Fibonacci number

by RoRi

July 10, 2015

We use the following recursive definition of the Fibonacci numbers,

$a_1 = 1, \qquad a_2 = 2, \qquad a_{n+1} = a_n + a_{n-1} \quad \text{if } n \geq 2.$

Prove that for all $n \geq 1$ we have,

$a_n < \left( \frac{1+\sqrt{5}}{2} \right)^n.$

Proof. For the case $n = 1$ , we have $a_1 =1$ and

$\left( \frac{1+\sqrt{5}}{2} \right)^1 = \frac{1+\sqrt{5}}{2} > 1 \qquad (\text{since } \sqrt{5} > 2).$

So, the inequality is true for $n=1$ . Assume then that the inequality is true for some $n = k \in \mathbb{Z}_{\geq 1}$ . Then,

$\begin{align*} a_k + a_{k-1} &< \left( \frac{1+\sqrt{5}}{2} \right)^k + \left( \frac{1+\sqrt{5}}{2} \right)^{k-1} \\ \implies \qquad \qquad a_{k+1} &< \left( \frac{1+\sqrt{5}}{2} \right)^{k-1} \cdot \left( \frac{1+\sqrt{5}}{2} + 1 \right) \\ &= \left( \frac{1 + \sqrt{5}}{2} \right)^{k-1} \cdot \left( \frac{3+\sqrt{5}}{2} \right). \end{align*}$

But, as one can compute, $\left( \frac{3+\sqrt{5}}{2} \right) = \left( \frac{1+\sqrt{5}}{2} \right)^2$ . Hence,

$a_{k+1} < \left( \frac{1+\sqrt{5}}{2} \right)^{k+1}.$

Thus, the inequality holds for all $n \in \mathbb{Z}_{\geq 1}. \qquad \blacksquare$

Prove an inequality on the ratio of n! to the nth power of n

by RoRi

July 10, 2015

Prove

$\frac{n!}{n^n} \leq \left( \frac{1}{2} \right)^k$

where $n \geq 2$ and $k$ is the greatest integer less than or equal to $n/2$ .

Proof. The proof is by induction. For the case $n=2$ we have on the left,

$\frac{n!}{n^n} = \frac{2!}{2^2} = \frac{1}{2}.$

On the right, we have

$\left( \frac{1}{2} \right)^k = \frac{1}{2}$

since $n/2 = 2/2 = 1$ implies $k = 1$ (since 1 is the greatest integer less than or equal to $n/2$ ).
Assume then that the inequality is true for some $n = m \in \mathbb{Z}_{\geq 2}$ . Then,

$\begin{align*} &&\frac{m!}{m^m} &\leq \left( \frac{1}{2} \right)^k \\ \implies && \left( \frac{m!}{m^m} \right) \left( \frac{(m+1)m^m}{(m+1)^{m+1}} \right) &\leq \left( \frac{1}{2} \right)^k \left( \frac{(m+1) m^m}{(m+1)^{m+1}} \right) \\ \implies && \frac{(m+1)!}{(m+1)^{m+1}} &\leq \left( \frac{1}{2} \right)^k \cdot \left( \frac{m}{m+1} \right)^m. \end{align*}$

But, from part (b) of this exercise we have

$m^p < \frac{(m+1)^{p+1} - m^{p+1}}{p+1}$

for all $p \in \mathbb{Z}_{>0}$ (and, in particular, must hold for $m-1$ , which will use in the following). So,

$\begin{align*} &&(p+1)m^p &< (m+1)^{p+1} - m^{p+1} \\ \implies&& m^{p+1} + (p+1)m^p &< (m+1)^{p+1} \\ \implies && m^m + m^m &< (m+1)^m & (\text{let } p = m-1)\\ \implies && 2m^m &< (m+1)^m \\ \implies && \left(\frac{m}{m+1} \right)^m &< \frac{1}{2}. \end{align*}$

Thus, we plug this back in to the inequality above and have,

$\frac{(m+1)!}{(m+1)^{m+1}} \leq \left( \frac{1}{2}\right)^k \cdot \left( \frac{m}{m+1} \right)^m \leq \left(\frac{1}{2}\right)^{k+1}.$

Notice that the inequality we have arrived at as $(1/2)^{k+1}$ as opposed to the $(1/2)^k$ we want. This is to deal with the fact that $k$ is the greatest integer in $m/2$ . This takes care of that problem since to complete the proof by induction we need to show that if the inequality holds for $m$ , then it holds for $m+1$ . If $m$ is even, then $k = m/2$ and $k+1 = (m+1)/2$ . On the other hand, if $m$ is odd, then $k = (m+1)/2$ . In either case though we have, $k+1 \leq (m+1)/2$ , so

$\frac{(m+1)!}{(m+1)^{m+1}} \leq \left( \frac{1}{2} \right)^{k+1} \leq \left( \frac{1}{2} \right)^{\lfloor \frac{m+1}{2}\rfloor}.$

Hence, the inequality holds for the case $m+1$ if it is true for any $m \in \mathbb{Z}$ .
Thus, the inequality is true for all $n \in \mathbb{Z}_{\geq 2}. \qquad \blacksquare$

Prove a generalization of Bernoulli’s inequality

by RoRi

July 10, 2015

For real numbers $a_1, \ldots, a_n$ with $a_i > -1$ for all $i = 1, \ldots, n$ and all of the $a_i$ having the same sign, prove

$(1+a_1)(1+a_2) \cdots (1+a_n) \geq 1 + a_1 + a_2 + \cdots + a_n.$

As a special case let $a_1 = \cdots = a_n = x$ and prove Bernoulli’s inequality,

$(1+x)^n \geq 1 + nx.$

Finally, show that if $n > 1$ then equality holds only when $x = 0$ .

Proof. The proof is by induction. For the case $n =1$ , we have,

$(1+a_1) = 1 + a_1 \qquad \implies \qquad 1+a_1 \geq 1+a_1,$

so the inequality holds for $n=1$ .
Assume then that the inequality holds for some $n = k \in \mathbb{Z}_{>0}$ . Then,

$\begin{align*} &&(1+a_1) \cdots (1+a_k) &\geq 1 + a_1 + \cdots + a_k \\ \implies&& (1+a_1) \cdots (1+a_k)(1+a_{k+1}) &\geq (1+a_1 + \cdots + a_k)(1+a_{k+1})\\ &&&\geq (1+a_1+ \cdots + a_{k+1})+a_{k+1}(a_1 + \cdots + a_k). \end{align*}$

But, $a_{k+1}(a_1 + \cdots + a_k) \geq 0$ since every $a_i$ must have the same sign (thus, $a_{k+1}$ and $(a_1 + \cdots + a_k)$ must have the same sign, so the product is positive). Thus,

$(1+a_1) \cdots (1+a_{k+1}) \geq 1+a_1 + \cdots + a_{k+1}.$

Hence, the inequality holds for the case $k+1$ ; and therefore, for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$

Now, if $a_1 = \cdots = a_n = x$ where $x > -1$ and $x \neq 0$ we apply the theorem above to obtain Bernoulli’s inequality,

$(1+a_1) \cdots (1+a_n) = (1+x)^n \geq 1+a_1 + \cdots + a_n = 1+n \cdot x.$

Claim: Equality holds in Bernoulli’s inequality if and only if $x = 0$ .
Proof.
If $x = 0$ then $(1+x)^n = 1 = 1 + n \cdot x$ , so indeed equality holds for $x = 0$ . Next, we use induction to show that if $x \neq 0$ , then the inequality must be strict. (Hence, equality holds if and only if $x = 0$ .)
For the case $n=2$ , on the left we have,

$(1+x)^2 = 1+2x + x^2 > 1+2x$

since $x^2 > 0$ for $x \neq 0$ . So, the inequality is strict for the case $n =2$ . Assume then that the inequality is strict for some $n = k \in \mathbb{Z}_{>1}$ . Then,

$\begin{align*} (1+x)^k > 1+kx\ &\implies & (1+x)^k (1+x) &> (1+kx)(1+x) &(x>-1 \implies 1+x>0)\\ &\implies & (1+x)^{k+1} &> 1 + (k+1)x + kx^2 \\ &\implies & (1+x)^{k+1} &> 1+(k+1)x. \end{align*}$

Where the final line follows since $k > 0$ and $x > 0$ implies $kx^2 > 0$ . Therefore, the inequality is strict for all $n > 1$ if $x \neq 0$ .

Hence, the equality holds if and only if $x = 0. \qquad \blacksquare$

Prove a formula for b^p – a^p and a resulting inequality

by RoRi

July 10, 2015

Prove that for any $p \in \mathbb{Z}_{>0}$ we have
$b^p - a^p = (b-a)(b^{p-1} + b^{p-2}a + b^{p-3} a^2 + \cdots + ba^{p-2} + a^{p-1}).$
For $p \in \mathbb{Z}_{>0}$ and $n \in \mathbb{Z}_{>0}$ prove that
$n^p < \frac{(n+1)^{p+1} - n^{p+1}}{p+1} < (n+1)^p.$
Again for $n,p \in \mathbb{Z}_{>0}$ prove
$\sum_{k=1}^{n-1} k^p < \frac{n^{p+1}}{p+1} < \sum_{k=1}^n k^p.$

Proof. First we rewrite the sum on the right in summation notation, and then use the distributive property to compute,

$\begin{align*} (b-a) (b^{p-1} + b^{p-2}a + \cdots + &ba^{p-2} + a^{p-1}) \\ &= (b-a)\left(\sum_{k=0}^{p-1} b^{p-k-1} a^k \right) \\ &= b \left( \sum_{k=0}^{p-1} b^{p-k-1} a^k \right) - a \left( \sum_{k=0}^{p-1} b^{p-k-1}a^k \right) \\ &= \sum_{k=0}^{p-1} b^{p-k} a^k - \sum_{k=0}^{p-1} b^{p-k} a^{k+1} \\ &= \sum_{k=0}^{p-1} b^{p-k} a^k - \sum_{k=1}^p b^{p-k} a^k & (\text{reindexing 2nd sum})\\ &= b^p + \sum_{k=1}^{p-1} b^{p-k} a^k - \left(\left(\sum_{k=1}^{p-1} b^{p-k} a^k\right) + a^p \right) \\ &= b^p - a^p & (\text{sums cancel}). \end{align*}$

This is the identity requested $. \qquad \blacksquare$
Proof. From the Binomial theorem we have

$(n+1)^{p+1} = \sum_{k=0}^{p+1} \binom{p+1}{k} n^k.$

Thus,

$\begin{align*} \frac{(n+1)^{p+1} - n^{p+1}}{p+1} &= \left(\frac{1}{p+1}\right) \left( \left(\sum_{k=0}^{p+1} \binom{p+1}{k}n^k \right) - n^{p+1} \right)\\ &= \left( \frac{1}{p+1} \right) \left(n^{p+1} + (p+1)n^p + \left( \sum_{k=2}^{p+1} \binom{p+1}{k} n^k \right) - n^{p+1}\right)\\ &= n^p + \left(\frac{1}{p+1} \right) \left( \sum_{k=2}^{p+1} \binom{p+1}{k} n^k \right)\\ &> n^p \end{align*}$

since the second term is strictly positive for $n,p$ positive integers. This establishes the inequality on the left.
For the inequality on the right we use part (a) to get,

$(n+1)^{p+1} - n^{p+1} = (n+1-n) \cdot ((n+1)^p + n(n+1)^{p-1} + \cdots + n^{p-1} (n+1) + n^p ).$

Thus,

$\begin{align*} \frac{(n+1)^{p+1} - n^{p+1}}{p+1} &= \left( \frac{1}{p+1} \right) \left((n+1)^p + n(n+1)^{p-1} + \cdots + n^{p-1}(n+1) + n^p\right) \\ &< \left( \frac{1}{p+1} \right) ((n+1)^{p+1} + (n+1)^p + \cdots + (n+1)^p) \\ &= \left( \frac{1}{p+1} \right) ((p+1)(n+1)^p) \\ & = (n+1)^p. \end{align*}$

In the second to last line we have just replaced each term $n$ in the sum by $n+1$ , giving the inequality. This establishes both sides of the requested inequality $. \qquad \blacksquare$
Proof. The proof is by induction. For the case $n= 1$ we have,

$\sum_{k=1}^{n-1} k^p = \sum_{k=1}^0 k^p =0, \qquad \frac{n^{p+1}}{p+1} = \frac{1}{p+1}, \qquad \sum_{k=1}^n k^p = \sum_{k=1}^1 k^p = 1.$

For a positive integer $p$ , then $0 < \frac{1}{p+1} < 1$ ; hence, the inequalities hold in the case $n =1$ . Assume then that they hold for some $n = m \in \mathbb{Z}_{>0}$ .
For the left inequality,

$\begin{align*} \sum_{k=1}^{m-1} k^p < \frac{m^{p+1}}{p+1} &&\implies \sum_{k=1}^m k^p &< \frac{m^{p+1}}{p+1} + m^p \\ &&&< \frac{m^{p+1} + (m+1)^{p+1} - m^{p+1}}{p+1} &(\text{part (b)})\\ &&&= \frac{(m+1)^{p+1}}{p+1}. \end{align*}$

This establishes the left inequality for all $n \in \mathbb{Z}_{>0}$ .
For the right inequality, assume it is true for some $n = m \in \mathbb{Z}_{>0}$ , then

$\begin{align*} \frac{m^{p+1}}{p+1} < \sum_{k=1}^m k^p \ &\implies& \frac{m^{p+1}}{p+1} + (m+1)^p &< \sum_{k=1}^{m+1} k^p \\ &\implies& \frac{m^{p+1} + (m+1)^{p+1} - m^{p+1}}{p+1} &< \sum_{k=1}^{m+1} k^p & (\text{part (b)})\\ &\implies& \frac{(m+1)^{p+1}}{p+1} &< \sum_{k=1}^{m+1} k^p. \end{align*}$

Hence, the right inequality is true for all $n \in \mathbb{Z}_{>0}$ . Therefore, the inequalities requested are indeed true for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$

Find all positive integers such that 2^n < n!

by RoRi

July 9, 2015

Claim: $2^n < n!$ holds for all positive integers $n \geq 4$ , and no others.
Proof. To show that it does not hold for $n=1,2,3$ we compute:

$2^1=2 \not< 1!=1, \qquad 2^2 = 4 \not< 2! = 2, \qquad 2^3 = 8 \not< 3! = 6.$

Now, for the case $n=4$ on the left we have

$2^n = 2^4 = 16.$

While, on the right we have,

$n! = 4! = 24.$

Since 16 is indeed less than 24, we the inequality holds for $n =4$ . Assume then that the inequality holds for some $n =k \in \mathbb{Z}_{\geq 4}$ . Then,

$2^k < k! \ \implies \ (2^k)(k+1) < (k!)(k+1) \ \Righarrow \ 2^{k+1} < (k+1)!.$

Where the last inequality uses the fact that since $k \geq 4 > 2$ so $2^k (k+1) > (2^k)\cdot2 = 2^{k+1}$ . Thus, the inequality holds for the case $k+1$ ; and hence, for all $n \in \mathbb{Z}_{\geq 4}. \qquad \blacksquare$

Prove inequalities relating a real number x to integer powers of x

by RoRi

July 9, 2015

Prove that for $n \geq 2$ ,

$x^n> x \qquad \text{if } x > 1$

and

$x^n < x \qquad \text{if } 0 < x < 1.$

Proof #1. Assume $x > 1$ . Then, if $n = 2$ we have

$x > 1 \ \implies \ x \cdot x > 1 \cdot x \ \implies \ x^2 > x.$

Where $x > 1$ implies $x > 0$ so multiplying both sides by $x$ preserves the inequality. So, the statement is true for $n =2$ . Assume then that the statement is true for some $n = k \in \mathbb{Z}_{\geq 2}$ . Then,

$\begin{align*} x^k > x &\implies& x^k \cdot x &> x\cdot x \\ &\implies& x^{k+1} &> x^2 \\ &\implies& x^{k+1} &> x & (\text{Since } x^2 > x.) \end{align*}$

Thus, the statement holds for $k+1$ ; and hence, for all $n \in \mathbb{Z}_{> 0}. \qquad \blacksquare$

Proof #2. Assume $0 < x < 1$ . Then, for the case $n=2$ we have

$x < 1 \ \implies \ x^2 < x$

since $0 < x < 1$ still allows us to preserve the inequality after multiplying both sides by $x$ . So, the inequality holds for the case $n=2$ . Assume then that it holds for some $n = k \in \mathbb{Z}_{\geq 2}$ . Then,

$\begin{align*} x^k < x &\implies& x^k \cdot x & < x\cdot x \\ &\implies& x^{k+1} &< x^2 \\ &\implies& x^{k+1} &< x &(\text{Since } x^2 < x). \end{align*}$

Thus, the inequality holds for $k+1$ ; and hence, for all $k \in \mathbb{Z}_{\geq 2}. \qquad \blacksquare$

Conjecture an inequality for products

by RoRi

July 9, 2015

If $a_k < b_k$ for $k = 1, \ldots, n$ , what conditions are needed for the inequality

$\prod_{k=1}^n a_k < \prod_{k=1}^n b_k$

to hold?

Claim: In addition to $a_k < b_k$ we also need $0 \leq a_k$ for each $k = 1, \ldots, n$ .
Proof. The statement is certainly true for the case $n=1$ (since $a_1 < b_1$ by assumption). Assume then that it is true for some $n = m \in \mathbb{Z}_{>0}$ . Then,

$\prod_{k=1}^{m+1} a_k = a_{m+1} \cdot \prod_{k=1}^m a_k < a_{m+1} cdot \prod_{k=1}^m b_k$

by the inductive hypothesis. But then, since $b_{m+1} > a_{m+1} \geq 0$ ,

$a_{m+1} \cdot \prod_{k=1}^m b_k < b_{m+1} \cdot \prod_{k=1}^m b_k = \prod_{k=1}^{m+1} b_k.$

Thus, the statement is true for $m+1$ ; and hence, for all $n \in \mathbb{Z}_{> 0}. \qquad \blacksquare$

Use an induction and properties of the product to prove an identity

by RoRi

July 9, 2015

Prove the identity:

$\prod_{k=1}^n \left( 1 + x^{2^{k-1}} \right) = \frac{1-x^{2^n}}{1-x}$

for $x \neq 1$ .

Proof. For the case $n=1$ on the left we have,

$\prod_{k=1}^n \left(1+x^{2^{k-1}}\right) = \prod_{k=1}^1 \left(1 + x^{2^{k-1}}\right) = 1+x^{2^0} = 1+x.$

While, on the right we have,

$\frac{1-x^{2^n}}{1-x} = \frac{1-x^2}{1-x} = \frac{(1-x)(1+x)}{1-x} = 1+x.$

So, the identity holds in the case $n=1$ . Assume then that it holds for some $n = m \in \mathbb{Z}_{>0}$ . Then we have,

$\begin{align*} \prod_{k=1}^{m+1} \left( 1+ x^{2^{k-1}} \right) &= \left( 1 + x^{2^m} \right) \cdot \prod_{k=1}^m \left(1 + x^{2^{k-1}} \right) \\ &= \left( 1 + x^{2^m} \right) \cdot \left( \frac{1-x^{2^m}}{1-x} \right) \\ &= \frac{\left(1+x^{2^m}\right)\left(1-x^{2^m}\right)}{1-x} \\ &= \frac{1-x^{2^{m+1}}}{1-x}. \end{align*}$

Hence, the statement is true for $m+1$ , and so, for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$

Prove the telescoping property of products

by RoRi

July 9, 2015

Use induction to prove that if $a_k \neq 0$ for all $k = 0, \ldots, n$ , then

$\prod_{k=1}^n \frac{a_k}{a_{k-1}} = \frac{a_n}{a_0}.$

This is the telescoping property for products.

Proof. For the case $n=1$ we have,

$\prod_{k=1}^1 \frac{a_k}{a_{k-1}} = \frac{a_1}{a_0}.$

Thus, the property holds for the case $n=1$ . Assume then that it holds for some $n = m \in \mathbb{Z}_{>0}$ . Then,

$\prod_{k=1}^{m+1} \frac{a_k}{a_{k-1}} = \left( \frac{a_{m+1}}{a_m} \right) \cdot \prod_{k=1}^m \frac{a_k}{a_{k-1}} = \left( \frac{a_{m+1}}{a_m} \right) \left( \frac{a_m}{a_0} \right) = \frac{a_{m+1}}{a_0}.$

Hence the property is true for $m+1$ ; and thus, for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$