Originally Posted by

**algebrapro18** I have a question on how to finish a proof by counter example and how to even start a set proof(I am horrable at them).

3. n < 2^n for every natural number n

Pf: Assume that this statement is false, i.e.

there exists a natural number x such that x ≥ 2^x .

Let X = {natural number n : n ≥ 2^n }

= > X ≠ the empty set

=> This set X has the smallest x in X such that x is greater than or equal to 2^x . Note that x is not 0 because 0 is not greater than or equal to 2^0 = 1.

=> 0 ≤ x-1 < x

=> x-1 is not in X

=> x -1 is less than 2^(x-1)