Thread: Inequalities

Can anyone help confirm if I have solved this correctly. Specifically the part preceded by A, where I have defined the coefficient as 2^k. I had originally thought that it might to be 2^k-1, but subbing 3 into that version yielded negative answers.

Many thanks.
​
Q. n! > 2^n-1 for n > 3, n

Attempt: Step 1: For n = 3...
3! = 1 x 2 x 3 = 6 & 2^3-1 = 4
Since 6 > 4, the statement is true for n = 3.

Step 2: Assume the statement is true for n = k, i.e. assume k! > 2^k-1
We must now show that the statement is true for n = k + 1,
i.e. (k + 1)! > 2^(k+1)-1 = (k + 1)! > 2^k
(k + 1)! = (k + 1)k! > (k + 1)2^k-1...(k! > 2^k-1...assumed)
If it can be shown that (k + 1)2^k-1 > 2^(k+1)-1, then (k + 1)! > 2^k
If (k + 1)2^k-1 > 2^k
If (k + 1)2^k-1 - 2^k > 0
A: If 2^k[(k + 1)2^k-2 - 1] > 0...true when > 3
(k + 1)! > 2^k
Therefore, the statement is true for n = k + 1, if true for n = k. Thus the statement is true for all n > 3, n

Your argument preceding step A is correct but the following step is incorrect

Originally Posted by GrigOrig99

A: If 2^k[(k + 1)2^k-2 - 1] > 0...true when > 3

it has to be .

~Kalyan.

Originally Posted by GrigOrig99

i.e. (k + 1)! > 2^(k+1)-1 = (k + 1)! > 2^k

It's OK to write = between numbers, but between propositions (which can be true or false). The notation "x > y = y' > z" is confusing and ambiguous. Use "iff" or "⇔" to claim that two propositions are equivalent.

Originally Posted by GrigOrig99

If (k + 1)2^k-1 - 2^k > 0
A: If 2^k[(k + 1)2^k-2 - 1] > 0...true when > 3

(k + 1)2^k-1 - 2^k ≠ 2^k[(k + 1)2^k-2 - 1] because 2^k[(k + 1)2^k-2 - 1] = (k + 1)2^2k-2 - 2^k. Rather, (k + 1)2^k-1 - 2^k = 2^k-1(k + 1 - 2).

Finally, an (informal) proof should be a correct English text. In particular, all sentences should be complete. You use phrases like "If (k + 1)2^k-1 - 2^k > 0" that are not complete sentences. I believe you showed an example from the book that said "A if B if C ..." meaning that C implies B, which implies A. This at least can be considered as a complete sentence. In your case, "If" with a capital "I" starts a new sentence with no "then." I prefer a chain of equalities and inequalities like this:

(k + 1)! = (k +1)k! > (by IH)
(k + 1)2^k-1 > (since k + 1 > 2 for k ≥ 3)
2 * 2^k-1 =
2^k

Great. Thank you.