Decide whether or not the following quantified propositions are true or false, where in each case the universal set is the set of positive integers N+. Justify each of your conclusions with a proof or a counterexample. (a) ∀n(2 n ≥ n 2 ) (b) ¬∃n(n 2 = 15)
The Answer to the Question
is below this banner.
Here's the Solution to this Question
(a) We should decide whether for all positive integers n, the inequality 2n>=n2 holds.
The statement is false. For n=3 we have that 23=8<9=32.
But for all positive integers this inequality holds.
For n=1 we have 2>1, for n=2 we have 22=22. To prove that the inequality holds for n>=4 we will use mathematical induction. The base case is n=4, 24=42. Let us prove the inductive step. Suppose that 2n>=n2. Then 2n+1=2 2n>2n2 by induction hypothesis. Since n>=4, we have that n2>2n+1. Hence, 2n2>n2+2n+1=(n+1)2.Thus, 2n+1>(n+1)2. Since both the base case and the inductive step have been performed, by mathematical induction the inequality holds for all n>=4.
(b) The function is monotone. We have that 32=9, 42=16. Thus, it does not exist positive integer n such that n2=15. The statement is true.