Home » Induction » Page 2

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

Given . Then if

prove that

with equality if and only if .

Proof. We consider two cases: the first one is the case that , and the second is the case that for at least one in .
Case #1: If , then

Thus, the inequality holds (in fact, equality holds).
Case #2: Now for the case that at least one of the . The proof is by induction on the number of terms . For the case , we have , 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,

Where the final inequality follows since since by assumption. Therefore, the inequality indeed holds for the case .
Assume then that the inequality holds for some . Then, let with for at least one . If , then there must be some such that (otherwise, if for all , then ). Similarly, if , then there is some such that . Hence, we have a pair, 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 and . Then, define . So,

Further, since (since one of is greater than 1 and the other is less than 1, so one of is positive and the other is negative), we have

Thus,

Hence, the inequality holds for ; and therefore, for all

# Prove an inequality for the nth Fibonacci number

We use the following recursive definition of the Fibonacci numbers,

Prove that for all we have,

Proof. For the case , we have and

So, the inequality is true for . Assume then that the inequality is true for some . Then,

But, as one can compute, . Hence,

Thus, the inequality holds for all

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

Prove

where and is the greatest integer less than or equal to .

Proof. The proof is by induction. For the case we have on the left,

On the right, we have

since implies (since 1 is the greatest integer less than or equal to ).
Assume then that the inequality is true for some . Then,

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

for all (and, in particular, must hold for , which will use in the following). So,

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

Notice that the inequality we have arrived at as as opposed to the we want. This is to deal with the fact that is the greatest integer in . This takes care of that problem since to complete the proof by induction we need to show that if the inequality holds for , then it holds for . If is even, then and . On the other hand, if is odd, then . In either case though we have, , so

Hence, the inequality holds for the case if it is true for any .
Thus, the inequality is true for all

# Prove a generalization of Bernoulli’s inequality

For real numbers with for all and all of the having the same sign, prove

As a special case let and prove Bernoulli’s inequality,

Finally, show that if then equality holds only when .

Proof. The proof is by induction. For the case , we have,

so the inequality holds for .
Assume then that the inequality holds for some . Then,

But, since every must have the same sign (thus, and must have the same sign, so the product is positive). Thus,

Hence, the inequality holds for the case ; and therefore, for all

Now, if where and we apply the theorem above to obtain Bernoulli’s inequality,

Claim: Equality holds in Bernoulli’s inequality if and only if .
Proof.
If then , so indeed equality holds for . Next, we use induction to show that if , then the inequality must be strict. (Hence, equality holds if and only if .)
For the case , on the left we have,

since for . So, the inequality is strict for the case . Assume then that the inequality is strict for some . Then,

Where the final line follows since and implies . Therefore, the inequality is strict for all if .

Hence, the equality holds if and only if

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

1. Prove that for any we have

2. For and prove that

3. Again for prove

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

This is the identity requested

2. Proof. From the Binomial theorem we have

Thus,

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

Thus,

In the second to last line we have just replaced each term in the sum by , giving the inequality. This establishes both sides of the requested inequality

3. Proof. The proof is by induction. For the case we have,

For a positive integer , then ; hence, the inequalities hold in the case . Assume then that they hold for some .
For the left inequality,

This establishes the left inequality for all .
For the right inequality, assume it is true for some , then

Hence, the right inequality is true for all . Therefore, the inequalities requested are indeed true for all

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

Claim: holds for all positive integers , and no others.
Proof. To show that it does not hold for we compute:

Now, for the case on the left we have

While, on the right we have,

Since 16 is indeed less than 24, we the inequality holds for . Assume then that the inequality holds for some . Then,

Where the last inequality uses the fact that since so . Thus, the inequality holds for the case ; and hence, for all

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

Prove that for ,

and

Proof #1. Assume . Then, if we have

Where implies so multiplying both sides by preserves the inequality. So, the statement is true for . Assume then that the statement is true for some . Then,

Thus, the statement holds for ; and hence, for all

Proof #2. Assume . Then, for the case we have

since still allows us to preserve the inequality after multiplying both sides by . So, the inequality holds for the case . Assume then that it holds for some . Then,

Thus, the inequality holds for ; and hence, for all

# Conjecture an inequality for products

If for , what conditions are needed for the inequality

to hold?

Claim: In addition to we also need for each .
Proof. The statement is certainly true for the case (since by assumption). Assume then that it is true for some . Then,

by the inductive hypothesis. But then, since ,

Thus, the statement is true for ; and hence, for all

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

Prove the identity:

for .

Proof. For the case on the left we have,

While, on the right we have,

So, the identity holds in the case . Assume then that it holds for some . Then we have,

Hence, the statement is true for , and so, for all

# Prove the telescoping property of products

Use induction to prove that if for all , then

This is the telescoping property for products.

Proof. For the case we have,

Thus, the property holds for the case . Assume then that it holds for some . Then,

Hence the property is true for ; and thus, for all