Answer/Do the following.
NOTE: Any item with exactly the same solution as the solution of any of your classmates shall
NOT be given points.
I. Prove the following by using mathematical induction. (14 points each)
1. 2n-1 n!
Proof:
Step 1: Verification
for n=1
n−1
2 ≤n !
1−1
2 ≤1!
0
2 ≤1
1 ≤1
Step 2: Form the Hypothesis
for n=k , Assume 2k−1 ≤ k !
Step 3: Proving
for n=k +1
n−1
2 ≤n ! Given
( k+1) −1
2 ≤(k +1)! Substitute k +1 for n
k
2 ≤ ( k +1 ) ! Simplify exponents.
k
2 ≤ ( k +1 ) k ! Definition of factorial
To show that
2k ≤ ( k +1 ) k !
We assume that 2k−1 ≤ k ! Step 2
k−1
Multiply both sides of inequality by 2
Simplify using laws of exponents
2(2 )≤ 2(k !)
k
2 ≤2 ( k ! )
Because 2 ≤ k +1 for k ≥ 1 by definition
of inequality
k
2 ≤2 ( k ! ) ≤ ( k +1 ) k ! for k ≥ 1
k
2 ≤ ( k +1 ) k ! Transitivity
Step 4: Since the statement is true for n-=1, and it is true for n=k+1 provided it is true for n=k, then
n−1
2 ≤n ! for n ≥ 1
2. 10n + 3(4n+2) + 5 is divisible by 9
Step 1: Verification
for n=1
10n + 3(4n+2) + 5 Given
=101 +3 ( 4 1+2 ) +5 Substitute 1 for n
=10+3 ( 43 ) +5 Simplify exponents
=10+3 ( 64 ) +5 evaluate exponential expression
=10+192+5 multiplication of numbers
=207 Addition of numbers
207 is divisible by 9
Step 2: Form the hypothesis
for n=k
10n + 3(4n+2) + 5
Assume 10k +3 ( 4k +2 ) +5 is divisible by 9
Step 3: Proving
for n=k +1
10n +3 ( 4n +2 ) +5 Given
¿ 10k +1+ 3 ( 4 k+1+ 2) + 5 substitute k +1 for n
¿ 10k +1+ 3 ( 4 k+3 ) +5 simplify exponents
¿ 10 ( 10k ) +3 ( 4 k+2 (4) ) +5 Applying Laws of Exponents
(Power of a product)
¿ 10 ( 10k ) +12 ( 4k +2 ) +5 Multiplication of numbers
¿ [ 9 ( 10 ) + ( 10 ) ]+[9 ( 4 ) + 3 ( 4 ) ]+5 Addition Property of
k k k+ 2 k+2
Exponential Expressions
¿ [9 (10¿¿ k )+9 ( 4k +2 ) ]+10k +3 ( 4k +2 ) +5 ¿ Regrouping
¿ 9(10 ¿ ¿ k + 4k +2)+10 k +3 ( 4 k+2 ) +5 ¿ Factoring
k +2
9(10 ¿ ¿ k + 4 )¿ is divisible by 9 Definition of divisibility
10k +3 ( 4k +2 ) +5 is divisible by 9 In Part 2, this is true
9(10 ¿ ¿ k + 4k +2)+10 k +3 ( 4 k+2 ) +5 ¿ is divisible by 9 If two numbers are divisible by a number,
their sum is also divisible by the number
Step 4: Since the statement is true for n-=1, and it is true for n=k+1 provided it is true for n=k,
therefore: 10n + 3(4n+2) + 5 is divisible by 9
3. For every natural number n, 1(1!) + 2(2!) + ... + n (n!) = (n + 1)! – 1
Step 1: Verification
for n=1
n(n !)=(n+1)! – 1 Given
⟹ 1 (1 ! )=( 1+1 ) !−1 Substitute 1 for n
⟹ 1 (1 ! )=2!−1 Addition of numbers
⟹ 1 (1 )=2−1 Simplification, definition of factorial
⟹ 1=1 Simplification, Operation of numbers
Step 2: Form the hypothesis
for n=k
1(1!) + 2(2!) + ... + n (n!) = (n + 1)! – 1 Given
Assume 1(1 !)+2(2 !)+ ...+ k (k !)=(k+ 1)! – 1
Step 3: Proving
for n=k +1
To Show that: 1 ( 1! )+ 2 ( 2 ! )+...+ ( k +1 ) ( k +1 ) !=[(k +1)+1]! – 1
⟹ 1 (1 ! )+2 ( 2 ! ) +...+ ( k + 1 )( k+ 1 ) !=(k +2)! – 1
1(1 !)+2(2 !)+ ...+ k (k !)=(k+ 1)! – 1 From Step 2, Assume
⟹ 1 (1 ! )+2 ( 2 ! ) +…+ k ( k ! ) + ( k+ 1 )( k +1 ) !
¿ ( k +1 ) ! – 1+ ( k +1 ) ( k +1 ) ! Add ( k +1 )( k + 1 ) ! both sides of the equation
¿ [ ( k + 1 ) !+ ( k +1 ) ( k +1 ) !]−1 regrouping
¿ [ ( k + 1 ) ! (1+k +1)]−1 factoring common binomial factor
¿ [ ( k + 1 ) ! (k +2)]−1 simplification
¿ ( k + 2 ) !−1 Simplification, definition of factorial
Therefore:
1 ( 1! )+ 2 ( 2 ! )+...+ ( k +1 ) ( k +1 ) !=(k +2)! – 1
Step 4: Since the statement is true for n-=1, and it is true for n=k+1 provided it is true for n=k
Hence, For every natural number n, 1(1!) + 2(2!) + ... + n (n!) = (n + 1)! – 1
II. Prove the following by using the uniqueness method. (15 points each)
1. If m and b are real numbers such that m 0, then there exists a unique real number x such that
mx + b = 0.
Part 1: Show Existence
Using construction method and from mx+ b=0,
−b
solving for x gives x=
m
Since m ≠0 , there exists a unique number x.
Part 2: Show Uniqueness
Assume that there exists another real number y.
b
By definition of uniqueness, y ≠−
m
And that my +b=0 must satisfy to make y a solution.
−b
Solving for y gives, y=
m
b
This contradicts the assumption that y ≠−
m
Hence, If m and b are real numbers such that m 0, then there exists a unique real number x
such that mx + b = 0.
2. If A and B are sets and f : A B is both one-to-one and onto, then for every element y B,
there is a unique element x A such that f(x) = y.
Part 1: Show Existence
To show existence, we use the definition of onto function. From the given that f is onto,
it means that for every y ∈ B , there ∃an x ∈ A such that f (x)= y .
Part 2: Show Uniqueness
Assume there exist two different elements x 1 and x 2 in A such that f (x 1)=f (x 2)= y .
Since f is one-to-one, and from the definition of one-to-one function, this implies x 1 = x 2 .
Therefore, the solution is unique.
Hence, If A and B are sets and f : A B is both one-to-one and onto, then for every
element y B, there is a unique element x A such that f(x) = y.
III. Do the following as required (14 points each).
1. Prove by using the either/or method: If x is a real number such that x3 + 2x2 - 4x – 8 0, then
x 2 or x -2.
Proof:
Method 1
Suppose x3 + 2x2 - 4x – 8 0 and x >−2
We need to show that x ≥ 2.
x3 + 2x2 - 4x – 8 0 Assumption
2
( x−2)( x + 4 x + 4)≥ 0 By factoring
(x−2)¿ By factoring
Since x >−2 Assumption
x +2>0 Addition Property of Inequality
and ( x +2 ¿ ¿2 ≥ 0 The square of a number is either 0 or a positive number
Then, (x−2)≥0 The product of 0 and/ or positive real numbers is always
greater than or equal to 0
Thus, x ≥ 2
Method 2
Suppose x3 + 2x2 - 4x – 8 0 and x <2
We need to show that x ≤−2.
x3 + 2x2 - 4x – 8 0 Assumption
2
( x−2)( x + 4 x + 4)≥ 0 By factoring
(x−2)¿ By factoring
Since x <2 Assumption
x−2<0 Addition Property of Inequality
But ( x +2 ¿ ¿2 ≥ 0 The square of a number is either 0 or a positive number
x +2≥ 0
It means that we cannot assume x <2
The Given is incorrect because the solution of x3 + 2x2 - 4x – 8 0 should be
x 2 or x = -2.
Checking Algebraically:
For x >2, take x=3
x3 + 2x2 - 4x – 8 0
3 2
3 +2(3) −4 ( 3 ) −8 ≥0
27+2 ( 9 )−12−8 ≥ 0
27+18−12−8 ≥ 0
45−20 ≥ 0
25 ≥ 0
For x=2,
x3 + 2x2 - 4x – 8 0
3 2
2 +2(2) −4 ( 2 )−8 ≥ 0
8+2 ( 4 )−8−8 ≥ 0
8+ 8−8−8 ≥ 0
0≥0
For x=−2,
x3 + 2x2 - 4x – 8 0
3 2
(−2) +2(−2) −4 (−2 )−8 ≥ 0
−8+2 ( 4 ) +8−8 ≥ 0
−8+ 8+8−8≥ 0
0≥0
For x ←2, take x=−3
x3 + 2x2 - 4x – 8 0
3 2
(−3) +2(−3) −4 (−3 )−8 ≥0
−27+ 2 ( 9 )+ 12−8 ≥ 0
−27+18+ 12−8 ≥ 0
30−35≥ 0
−5 ≥ 0
Therefore, the proposition Prove by using the either/or method: If x is a real number such that
x3 + 2x2 - 4x – 8 0, then x 2 or x -2 is wrong
2. Give an example of a true statement/proposition that may be proved using the
maximum/minimum method. Then write the detailed proof.
Proposition: If a , b∧c are real numbers with a> 0 and b ≠ 0, then
min { ax2 +bx +c : x is a real number }< c .
Proof:
You can convert the statement to, There exist a real number x such that
2
ax +bx +c <c .
Equivalently,
There exist a real number x such that ax 2 +bx <0 .
It is clearly that we should use the construction method to produce the real
number x.
Turning to the forward process, we know that b ≠ 0 and so,
Either b< 0 or b> 0
Recognizing the key words “either/or” in the forward process, a proof by cases
is appropriate.
Accordingly, assume
Case 1: b< 0
We must show that There exist a real number x such that
2
ax +bx=x ( ax +b )< 0.
In this case, because a> 0 from the hypothesis,
−b
>0.
a
−b
So, constructing x as any real number with > x> 0
a
We have shown that There exist a real number x such that
2
ax +bx=x ( ax +b )< 0.
Therefore, x ( ax+ b ) <0 because x >0∧ax +b<0.
Case 2: b> 0
We must show that There exist a real number x such that
2
ax +bx=x ( ax +b )< 0.
In this case, because a> 0 from the hypothesis,
b
>0.
a
b
So, constructing x as any real number with x <0<
a
We have shown that There exist a real number x such that
2
ax +bx=x ( ax +b )< 0.
Therefore, x ( ax+ b ) <0 because x <0∧ax +b>0.
Therefore, the proposition: If a , b∧c are real numbers with a> 0 and b ≠ 0,
then min { ax2 +bx +c : x is a real number }< c , is true.
