Mathematical Induction
/by admin_ctHow to prove a statement using mathematical induction?
Proving a statement by mathematical induction is a two-step process. The first step is called the basis step, and the second step is called the inductive step. Base step is generally easy and proved for n=1 or whatever the domain restriction given for n, whereas inductive step require logical thinking and sometimes use some algebraic operations. This process is used to prove variety of statements which are formulated in terms of n, where n is a positive integer.
How many types of mathematical induction is there?
We use two types of mathematical Induction : Weak Induction and Strong induction.
Both are similar in a way that both use the base case but how you prove the inductive step is slightly different for both types. Lets observe the difference.
What is the difference between strong induction and weak induction?
Spot the difference from the point of view of asking a domino why it is falling.
Weak induction: “I’m falling because the domino before me has fallen.”
Strong induction: “I’m falling because all the dominoes before me have fallen.”
Trivially, every statement provable by weak induction is also provable by strong induction, but it is not so obvious whether the converse holds.
Example1 :Prove using mathematical induction that for all n ≥ 1,
Lets assume P(n) be the given equation.
Basis step: We need to show that P(1) is true. Which means there is only first term.
Therefore, P(1) is true.
Inductive hypothesis: For all integers k≥1, suppose P(k) is true.
Inductive step: We will show that for all integers k≥1, if P(k) is true then P(k+1) is also true.
[by substitution from the inductive hypothesis]
Next, we simplify right side.
[Make the denominators same]
[ factored out ]
Above expression can be written as a squared function.
Which is actually the right hand side of P(k+1).
Therefore, statement is proved by mathematical induction.
Example 2: Use mathematical induction to prove for all integers 𝑛 > 6.
Since n is given greater than 6, so n value used for basis step will be 7.
Lets assume P(n) be the given equation.
Basis step: We need to show that P(7) is true.
which is true.
That shows P(7) is true.
Inductive hypothesis: For all integers k > 6, suppose P(k) is true.
Inductive step: We will show that for all integers k > 6, if P(k) is true then P(k+1) is also true.
[ using inductive hypothesis ]
[ 3 will always be less than k+1 as k is greater than 6 so 3 can be replaced with k+1 ]
Which proves that p(k+1) is true.
Therefore, statement is proved by mathematical induction.
Example 3: Use mathematical induction to prove that log(n!) ≤ nlog(n) for all integers, n≥1.
As given restriction is n≥1 so the n value used for basis step will be 1.
Lets assume P(n) be the given equation.
Basis step: We need to show that p(1) is true.
log(1)≤1(0)
0 ≤ 0
This shows p(1) is true.
Inductive hypothesis:
For all integers k ≥ 1, suppose P(k) is true.
Inductive step:
Next to show that for all integers k ≥1, if P(k) is true then P(k+1) is also true.
[ from inductive hypothesis ]
Adding log(k+1) to both sides,
[ Since log(k) ≤ log(k+1), so log(k) can be replaced with log(k+1) keeping inequality true ]
Which proves that p(k+1) is true.
Therefore, statement is proved by mathematical induction.
Example 4 : Prove by mathematical induction on the positive integers ∀𝑛𝑃(𝑛) where 𝑃(𝑛) is: If 𝐴1, 𝐴2, ⋯ , 𝐴𝑛 and 𝐵 are sets, then
Lets assume P(n) be the given equation.
Basis step: We need to show that p(1) is true.
This shows P(1) is true.
Inductive hypothesis:
For all integers k ≥ 1, suppose P(k) is true.
Inductive step:
Next to show that for all integers k ≥1, if P(k) is true then P(k+1) is also true.
[ from inductive hypothesis ]
Adding k+1th term to both sides,
[ using distributive law of sets (𝑋 ∩ 𝑌) ∪ 𝑍 = (𝑋 ∪ 𝑍) ∩ (𝑌 ∪ 𝑍)]
Which proves that p(k+1) is true.
Therefore, statement is proved by mathematical induction.
Here is an example for proof by strong induction.
Example 5: Consider a proof by strong induction of ∀𝑛𝑃(𝑛) where 𝑃(𝑛) is: If 𝑛 ≥ 12, then 𝑛 cents of postage can be formed by using only 3-cent stamps and 7-cent stamps.
let P(n) : If 𝑛 ≥ 12, then 𝑛 cents of postage can be formed by using only 3-cent stamps and 7-cent stamps.
Since n ≥ 12 , so we prove that P(12), P(13),P(14), P(15) is true for basis step.
P(12) : 4(3) Four 3-cent stamps can make 12 cents of postage.
P(13) : 2(3)+1(7) Two 3-cents stamps and one 7-cent stamp can make 13 cents of postage.
P(14) : 2(7) Two 7-cents stamps can make 14 cents of postage.
P(15): 5(3) Five 3-cents stamps can make 15 cents of postage.
This proves the basis step.
Inductive hypothesis:
For all integers k ≥ 12, suppose P(k) is true.
That means any amount of postage from 12 cents to k cents can be formed by using 3-cents and 7-cents stamps.
Inductive step:
Next to show that for all integers k ≥12, if P(k) is true then P(k+1) is also true. That means if any amount of postage from 12 cents to k cents can be formed by using 3-cents and 7-cents stamps then k+1 cents of postage can also be formed by using 3-cents and 7-cents stamps.
Since P(k) is true by inductive hypothesis, P(k-2) will also be true, where 12≤k-2≤k.
That means postage of k-2 cents can be made using 3 -cents and 7-cents stamps.
P(k+1) = P(k-2 +3)
P(k+1) = P[(k-2)+3]
Which represent postage of k+1 cents of postage can be made using k-2 cents of postage and an additional 3 cent stamp.
Which proves that p(k+1) is true.
Therefore, statement is proved by strong induction.
Practice problems:
- Prove the following by principle of mathematical induction.
2. Prove using mathematical induction that for all n≥4,
3. Prove that is divisible by 7 for all n≥0.
4. Prove the following by principle of mathematical induction.
How to solve linear inequalities with absolute sign?
/by admin_ctLinear inequalities with absolute sign are not as easy as simple linear inequalities. They can be divided into 4 cases depending on the inequality sign and positive or negative right side. All these cases are described in a table given below.
Case 1 | Case 2 | Case 3 | Case 4 |
or | or
|
||
or
After rewriting like this, we solve this compound inequality using rules of inequality to get x all by itself. |
x > a or x < -a
or After breaking the inequalities like this, expression can be solved further to get x by itself. |
Since absolute value is always positive, it can’t be less than or equal to any negative number so this case has no solution. | Since absolute value is always positive ,it would always be greater than any negative number so this case has ‘All real numbers ’ as solution. |
Lets work on some examples representing all the 4 cases to understand them better.
Example1. Solve the following inequality
Solution: This is of the form (case 1) , so rewriting the inequality we get,
-3 -3 -3 subtracting 3 from all sides, we get ,
In interval notation this solution can be written as [-9,6]
Example2. Solve the following inequality and write the solution in interval notation.
3|2x+1| > 9
Solution: First we isolate the absolute part. So divide both sides by 3 we get, |2x+1| > 3
This is of the form (case2) , so rewriting the inequality we get,
2x+1 > 3 or 2x+1 < -3
2x > 2 2x < -4
x > 1 or x < -2
Combining these two inequalities by replacing ‘or’ with U (union symbol) to write final answer in interval notation we get,
Example3. Solve the following inequality and write the solution in interval notation.
Solution: Subtract 8 from both sides to isolate absolute part we get,
This is of the form (case 3).
Since absolute value is always positive, so it can’t be less than or equal to any negative number. Therefore this inequality has No Solution.
Example4. Solve the following inequality and write the solution in interval notation.
Solution: Subtract 8 from both sides to isolate absolute part we get,
This is of the form (case 4).
Since absolute value is always positive, so it is always greater than any negative number. Therefore this inequality has ‘All Real numbers ’ as solution which can be written in interval notation as, (-∞,∞)
Inequalities with absolute sign having variables on both sides:
Inequalities having more than one absolute sign or having variable on both sides, are solved using different approach. We get the intervals on a number line according to expression inside absolute signs and then solve inequalities for each interval. Lets work on some examples to understand this process better.
Example5. Solve the given inequality and write the answer in interval notation.
|x-1|+|x-2| ≥ 4
Solution: First we set the expressions inside absolute signs =0 to get points on number line.
So x-1=0 => x=1 and x-2=0 => x=2
Using these two points, we get the intervals on number line as (-∞,1) ,(1,2) and (2,∞). Here we also make use of definition of absolute function.
For interval (-∞,1) we have the inequality as,
-(x-1)-(x-2) ≥ 4
-x+1-x+2 ≥ 4
-2x +3 ≥ 4
-2x ≥ 1
x ≤ -½ —–(i)
For interval (1,2) we have the inequality as,
(x-1) –(x-2) ≥ 4
x-1-x+2 ≥ 4
1 ≥ 4 (which is absurd )
For interval (2,∞), we have the inequality as,
(x-1) +(x-2) ≥ 4
2x -3 ≥ 4
2x ≥ 7
——–(ii)
Combining results (i) and (ii) we get the final solution in interval form as, (-∞ , -½] U [ 7/2 ,∞)
Example6. Solve the inequality |2x-3| > x-1
Solution: Taking positive and negative cases separately,
-(2x-3) > x-1 or 2x-3 > x-1
-2x+3 > x-1 2x-x > -1+3
-2x-x > -1-3 x > 2
-3x > -4
x < 4/3
Combining these two inequalities, we get the final answer in interval form as, (-∞, 4/3) U (2,∞)
Practice problems:
Solve the following inequalities and write the solution in interval form.
1) |3x-2| ≤ ½
2) |4-x| +1 > 3
3) |x-1|+|x-2|+|x-3|≥ 6
4) 4+|x-3| < 1
Answers:
1) [1/2 , 5/6]
2) (-∞,2) U(6,∞)
3) (-∞,0] U [4,∞)
4) No solution
How to solve linear inequalities with radicals ?
/by admin_ctLinear inequalities with radicals
While dealing with inequalities having square root (radical) , we also need to consider the domain of radical expressions. We take into consideration both the solutions, one which we get after solving inequality by squaring both sides and other by setting radicand ≥ 0. lets work on some examples to understand this process better.
Example1. Solve the following inequality and write the solution in interval form.
Solution:
Squaring both sides,
x – 1 ≤ 9
x ≤ 10 ——(i)
Since radicals are not defined for negative values so radicand must be positive. Therefore, x-1 ≥ 0
=> x ≥ 1 ——–(ii)
Combining the solutions (i) and (ii), we get final solution as,
1 ≤ x ≤ 10 => [1 ,10]
Example2. Solve the following inequality and write the solution in interval form.
Solution: Also,
x ≥ 3
(multiplied with -1 and inequality sign changed)
squaring both sides,
x -3 ≤ 36
x ≤ 39
combining two solutions we get, 3 ≤ x ≤ 39
Final answer in interval form [3,39]
Example3.Solve the following inequality and write the solution in interval form.
Solution: We can rewrite the given inequality as,
Since LCM of denominators 2 and 3 is 6 so we multiply exponents of both sides with 6 and get,
=>
As can never be negative so x-1 ≤ 0
x≤ 1 —— (i)
Also , being an even radical is never defined for negative values which restrict the given solution to x ≥ 0 —— (ii)
So final solution, after combining (i) and (ii) is given as,
0≤x≤1 => [0,1]
Example4. Solve the inequality
Solution: Rewriting the given inequality as,
Since lcm of denominators 2 and 4 is 4, So raising exponents on both sides by 4 and we get,
x ( x-16) ≥ 0
As we know that even radicals are not defined for negative values which restrict domain to x ≥ 0,
Also, x-16≥0 => x≥ 16
So final solution is given as, [16,∞)
Practice problems:
Solve the following inequalities and write the answer in interval form.
Answers:
- (0,1)
- [1/2, 5]
- [32,∞)
- ( -3/11 , 2)
How to solve linear inequalities ?
/by admin_ctSolving linear inequalities is similar to solving linear equations. All the rules and facts are same as for linear equation , only exception is that whenever we multiply or divide any inequality with a negative number, its sign get reversed. That means < sign get changed to > and viceversa.
Here are few examples to understand the process.
Example1. Solve the following inequality.
2(x-3) > 10
Solution:
(x-3) > 5
X > 5+3
X > 8
Now we work on same example but with a negative sign and see how it effect the solution.
Example2. Solve the following inequality.
-2(x-3) > 10
Solution: To get rid of -2 , we divide both sides by -2 and therefore inequality sign get reversed.
(x-3) < -5
X < -5+3 => x < -2
Representing the solution of an inequality : Solution of an inequality can be represented in two ways. One as an inequality and other as interval notation. To represent the solution in interval notation we need to be familiar with some rules.
Rules to convert the inequality in interval notation:
1) In interval notation smaller number is always written towards left (first place) and larger number is written towards right(second place). This rule would be helpful in solving double inequalities.
2) Solution having only < or > sign is represented with open brackets ( ) which means end points are not included
3) The solution having or is represented with closed brackets [ ] which means end points are included.
4) We always use parenthesis ( ) with infinity.
Here is a beautiful tabular representation of all these rules.
Representing the solution of inequality on a number line :
Inequality | Interval Notation | Number line representation |
a<x<b | (a,b) | |
a≤x≤b | [a,b) | |
a<x≤ b | (a,b] | |
a≤x ≤b | [a,b] | |
X<b | (-∞ ,b) | |
x>a | (a, ) | |
x ≤ b | (-, b] | |
x ≥ a | [a, ) |
Example3. Solve the following inequality and represent the solution as interval notation.
12-(2t+1) ≥ 2(t-5)
Solution: First we remove parenthesis , for that we distribute – sign on left and 2 on right side of the inequality.
12 -2t-1 2t-10
-2t -2t -10-12+1 (combining and rearranging like terms)
-4t -21
(inequality reversed when divided by negative number)
In interval notation answer can be written as,
Example4. Solve the following inequality and write the answer in interval notation. Also represent it on number line.
Solution: Distributing 1/5 we get,
Multiply both sides with -5/4 to get x by itself,
(inequality reversed when multiplied by negative number)
x 5
Interval notation: (- , 5]
How to solve Double inequality: Solving double inequality is similar to solving single inequality but here we don’t move the variable to one side and numbers to other side as we do in solving single inequality. Our target is to get x all by itself and to get that,we use same operation to both sides. That means if we add or subtract something to middle x term, we do the same operation to left and right side terms too.
Example5. Solve the following inequality and represent the solution in interval notation.
7 < 5+2x < 1
Solution: 7 < 5+2x < 1
-5 -5 -5 (subtracting 5 from all sides)
2 < 2x < -4
1 < x < -2
As per rules of writing interval notations, smaller number should be written first, so this inequality can be rewritten as,
-2 < x < 1
Which can be further written in interval notation as (-2,1)
Example6. Solve the given compound inequality and represent the solution in interval notation. Also represent the solution on number line. -10 < -5(x+2) 6
Solution: -10 < -5x-10 6 (distributed -5)
-10 < -5x-10 6
+10 +10 +10
0 < -5x 16
Writing this solution in proper format , we get interval notation as
=> [-3.2 ,0)
Practice problems:
Solve the following inequalities and represent the solutions in interval notation.
- 3(2x-5) -15
- -2(x+1) > 8-(x+5)
Solve the following compound inequalities and represent the solution on number line.
- -5 2x-1 3
- 9 3(x-1) -12
Answers:
- (- ,0]
- (- , -5)
- [-2,2]
- [-3,4]
Square root and Approximations
/by admin_ctSquare root and Approximations
To know about approximating square roots, first we should learn perfect squares because they are interrelated. Here is a table of perfect squares and square roots.
This way you can learn the square roots upto 50. Lets discuss the process of approximating square roots now.
There are many ways to approximate the square roots. The one which we are going to discuss, is the easiest and quicker one. Here are the steps:
1)First find the nearest perfect squares, in which the sqrt lie between.
2) Lets assume the sqrt number to be approximated as S, smaller perfect square as N and larger perfect square as N+1 such that
Then the approximation A is given by the following formula.
Lets work on some examples to understand the process
Example1. Approximate √34 to one decimal place.
Solution: √34 lie between √25 and √36 which are nearest perfect squares so,
Here S= 34 , N=5 , N+1=6
Using formula,
Example2. Approximate √70 to one decimal place.
Solution: √70 lie between √64 and √81 which are the nearest perfect squares so,
Here S= 70 , N=8 , N+1=9
Using formula,
The method discussed above gives you sqrt approximation upto one decimal place.
Second method: If you are on time constraint For SAT, ACT or any other test and you are given choices then we can fairly guess the right answer by finding the nearest perfect squares and distance of sqrt from the nearest perfect square.
For example we need to approximate √70 which lie between perfect squares 64 and 81.
Distance between 70 and its nearest perfect square 64 is 6 which is less then halfway (72.5) that means √70 would be approximated to a value less than 8.5 but closer to 8.5. Based on this observation we can guess the right answer out of the following options.
a) 7.8
b) 8.6
c) 8.4
d) 8.9
We are pretty sure about the right answer to be 8.4 because Only this option is less than 8.5 and closer to it.
To approximate √74 we choose 8.6 because 74 is more than halfway 72.5 and closer to it.
To approximate √ 79 we choose 8.9 because 79 is more than halfway 72.5 and more closer to 81 so it would be approximated closer to 9.
So when we are on a time constraint and have multiple choices , we can use above estimation process.
First method gives you the exact approximation upto one decimal place , second method also gives a pretty good estimation within seconds.
You can always check your results by using calculators.
Ptolemy’s Theorem
/by admin_ctIn a cyclic quadrilateral, the sum of product of two pairs of opposite sides equals the product of its diagonals.
Lets work on some examples on Ptolemy’s theorem.
What is the length of chord ? Explain your answer.
To solve this problem, we will use Ptolemy’s theorem.
For that we need to find other diagonal BD first using Pythagorean. So two cases arise here.
Case 1: BD is a diameter passing through center of circle.
Then ABD and BCD both are right triangles using Thales theorem.
[ applying Pythagorean in right triangle BAD ]
Case 2: BD is NOT a diameter.
Then ΔBAD and ΔBCD are congruent by SSS rule of congruency.
AB = BC = 2 [ given equal sides ]
AD = CD = 8 [ given equal sides ]
BD = BD [ common sides ]
[ by SSS rule of congruency ]
[ by CPCTE ]
Since ABCD is a cyclic quadrilateral , therefore sum of its apposite angles would be 180.
Here angles BAD and BCD are opposite angles of a cyclic quadrilateral and both are equal so each must be 90.
Therefore we can apply Pythagorean in any of the triangles to find side BD.
Once we have BD, we can apply Ptolemy’s theorem.
so we have,
[ by Ptolemy’s theorem ]
An equilateral triangle is inscribed in a circle, If P is a point on the circle, What does Ptolemy’s theorem have to say about the distances from this point to three other vertices ?
Lets join vertices B and C with point P. Now ABPC makes a cyclic quadrilateral. Ptolemy’s theorem can be applied here.
Since ΔABC is given equilateral, so we have its all three sides equal. Lets assume each side as x.
AB = BC = CA = x
Now replace AB, BC and CA with x in the first expression, and we get it as,
Dividing both sides of this equation by x, we get
Which can be summarized as under,
Larger distance, which is the distance from point P to vertex A is equal to sum of smaller distances to other two vertices.
Kite ABCD is inscribed in a circle. The kite has an area of 108 in².The ratio of lengths of non congruent adjacent sides is 3:1 . What is the perimeter of this kite?
To find side length of each side of kite, we make use of Ptolemy’s theorem. But before that we need to use area of kite formula.
Given ratio of lengths of non congruent adjacent sides = 3:1
Then we can write non congruent sides AD and AB as 3x and x, where x is the common ratio.
Using Ptolemy’s theorem,
x = 6 , accepting only positive value as distance measurements can never be negative.
So all the sides of Kite are given as,
3x = 3(6)= 18
x= 6
and perimeter of kite is given as,
18+6+18+6 = 48 inches
Practice problems:
- Draw a regular pentagon of side length 1 in a circle. Let b be the length of its diagonals. What does Ptolemy’s theorem say about quadrilateral formed by four of the vertices of Pentragon ?
- Prove Pythagorean theorem using Ptolemy’s theorem.
Equation of circle (general form)
/by admin_ctThe general form of the equation of circle is:
x2 + y2 + 2gx + 2fy + c = 0.
Its center and radius is given as :
Center : (-g,-f)
radius r :
Using above expression , we can tell some more information about circle ,
If Then it is a real circle with radius r.
If Then the circle coincides with its center and it would be just a point or called point circle.
If Then this circle won’t be possible as its radius would be an imaginary number. So the solution is empty set.
Identify the center and radius of a circle with the following equation.
First, compare the given equation with general equation of circle :
we get, 2g= -12
g = -6 ⇒ -g = 6
and 2f = -16
f = -8 ⇒ -f = 8
Therefore center of circle is given as : (6,8)
and radius is given as,
Find center and radius of a circle for the given equation using two ways. Firstly using general formula, secondly using standard formula by completing square method.
Using general formula , we compare the given equation with general equation
we get,
2g = 4 ⇒ g= 2
and
2f = -12 ⇒ f = -6
Therefore, we get center of circle as (-g, -f) = (-2,6)
and radius as
Using standard form , we complete the squares for both x and y terms.
[ added 4 and 36 on both sides to complete perfect squares ]
Comparing it with standard form:
we get center (h,k) = (-2,6)
and radius r²= 81 ⇒ r= 9
Stella says the equation has a center (4,-1) and radius of 5. Is she correct? why or why not ?
We can find its center using either of the above mentioned two methods.
Lets use completing square method.
[ added 16 and 1 on both sides to complete the squares]
Comparing it with standard form, we get center as (4,-1)
and radius r = √22
Stella is correct that center is (4,-1) . However she didn’t find the radius correctly. Correct radius is √22 not 5.
Identify the graphs of the following equations as a circle, a point or an empty set.
a)
To answer this question , it would be better to use general form and above mentioned rules for radius.
Rewriting the given equation in general form we get,
Now comparing the given equation with general equation of circle :
we get,
2g = 4 ⇒ g= 2
2f = 0 ⇒ f =0
c= 0
Using formula for radius ,
That means this is a real circle with radius 2.
b)
Comparing the given equation with general equation of circle :
we get,
2g = 6 ⇒ g= 3
2f = -4 ⇒ f = -2
c= 15
Using formula for radius ,
Since radius is an imaginary number , that means this circle not possible and its graph would be empty set.
c)
Comparing the given equation with general equation of circle :
we get,
2g = 6 ⇒ g= 3
2f = -4 ⇒ f = -2
c= 13
Using formula for radius ,
Since radius is 0 so this would be a point .
Practice problems:
Find center and radius of a circle for the given equation using two ways. Firstly using general formula, secondly using standard formula by completing square method.
a)
b)
Identify the graphs of the following equations as a circle, a point or an empty set.
a)
b)
c)
Equation of circle (standard form)
/by admin_ctEquation of a circle in standard form.
Equation of a circle which is centered at origin (0,0), with radius r, is given in standard form as:
Above equation can also be obtained using distance formula between points (0,0) and (x,y) . Distance between these two points is ‘r’
Equation of a circle in center-radius form is given as:
Equation of a circle with center (h,k) and radius r is written in standard form as:
Lets work on some problems based on circle:
Write the equation of a circle with center (-1,2) and radius as 5.
Here we have center (h,k) as (-1,2) and radius r= 5.
Now plugin these values into standard center -radius form of circle.
To get the general form of circle, we just need to expand the squares
How do you find the equation of a circle with center at the origin and passing through (-2, -3)?
Since the circle is centered at origin so we have center (h,k) as (0,0).
Now plugin given point (-2,-3) as (x,y) and (0,0) as center (h,k) into standard form.
Finally , we can write circle equation as,
State the coordinates of center and measure of radius for the circle whose equation is given as
Rewriting the given equation as ,
Comparing the given circle equation with standard form
we get h = 2
k = -3
and
r = 3 , as radius measure can’t be negative so we drop negative sign and get r= 3
Therefore, the center of given circle is (2,-3) and radius = 3
Find equation of a circle with the diameter that has end points at (0,1) and (2,5).
We know that mid point of diameter is the center of circle. So first we find center of circle using mid point formula.
Next step is to find radius which can be found two ways,
firstly, using distance formula on end points of diameter and making it half and
secondly , using distance formula on center and any end point of diameter.
Since second way is shorter so lets use this way.
Using distance formula on center (1,3) and end point (0,1) which is easier to use out of these two end points.
Since distance D is the radius r, we can plugin coordinates of center (h,k) and radius r into standard form