Prove that whenever n is a positive integer.
It is proved that .
The principle of mathematical induction is to prove that P(n) is true for all positive integer n in two steps.
1. Basic step : To verify that P(1) is true.
2. Inductive step : To prove the conditional statement if P(k) is true then P(k+1) is true.
Let P(n) be the statement . Let us prove by induction on n.
For n = 1 , the value of LHS is 1 and RHS is 1. Since, both are equal the statement is true for P(1) .
Assume that the statement is true for P(k) then prove for P(k+1) .
Let P(k) be true then . Let us prove the statement is true for as follows:
Further, simplify the values as follows:
Thus, P(k+1) is also true.
Therefore, the statement P(n) is true for every positive integer n.
Use the well-ordering principle to show that if x and y are real numbers with x<y, then there is a rational number r with x<r<y. [Hint: Use the Archimedean property, given in Appendix 1, to find a positive integer A with . Then show that there is a rational number with denominator A between x and y by looking at the numbers , where is a positive integer.]
Let be the statement that in a triangulation of a simple polygon with sides, at least one of the triangles in the triangulation has two sides bordering the exterior of the polygon.
a) Explain where a proof using strong induction that is true for all integers runs into difficulties.
b) Show that we can prove that is true for all integers by proving by strong induction the stronger statement for all integers , which states that in every triangulation of a simple polygon, at least two of the triangles in the triangulation have two sides bordering the exterior of the polygon.
94% of StudySmarter users get better grades.Sign up for free