Answer to Question #98297 in Discrete Mathematics for Ahmed

Question

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)

Answer 1

(a) We should decide whether for all positive integers n, the inequality 2ⁿ>=n² holds.

The statement is false. For n=3 we have that 2³=8<9=3².

But for all positive integers $n\neq 3$ this inequality holds.

For n=1 we have 2>1, for n=2 we have 2²=2². To prove that the inequality holds for n>=4 we will use mathematical induction. The base case is n=4, 2⁴=4². Let us prove the inductive step. Suppose that 2ⁿ>=n². Then 2ⁿ⁺¹=2$\times$ 2ⁿ>2n² by induction hypothesis. Since n>=4, we have that n²>2n+1. Hence, 2n²>n²+2n+1=(n+1)².Thus, 2ⁿ⁺¹>(n+1)². 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 $n\mapsto n^2$ is monotone. We have that 3²=9, 4²=16. Thus, it does not exist positive integer n such that n²=15. The statement is true.