Pages

Sunday, August 24, 2014

Solution of a cubic equation (Part 2)

In the post Solution of a cubic equation Part 1 we found the solution of a cubic equation for a particular condition. Then, in the post Whether real or complex (Cubic Equation) we studied when the roots of a cubic equation will be real and when it will be complex. This post deals with the solution of cubic equation. The algebraic method of solving cubic equations is supposed to be due to the Italian, del Ferro (1465-1526). But it is called Cardano's method because it became known to people after the Italian, Girolamo Cardano, published it in 1545 in his 'Ars Magna'.

Omar Khayyam gave a great deal of thought to the cubic equations. Before him, Greek mathematicians obtained solutions for third degree equations by considering geometric methods that involved the intersection of conics. Although the solution is present but I am searching for a solution of cubic equation with almost a new perspective. I will continue my search but I am giving this method so that until I find my kind of solution the traditional solution is present on my blog.

Let us consider the equation (ax3 + bx2 + cx + d = 0 ; a≠0)

Step 1: Express ax3 + bx2 + cx + d = 0
as x3 + px2 + qx + r = 0

Step 2: Shift the middle point of the curve on the axis x=−p/3.
Read post Solution of a cubic equation. A special solution and Why -b/3a? for detail.
x3 + 3(p/3)x2 + 3(p2/9)x + p3/27 − 3(p2/9)x − p3/27 +qx+ r = 0
(x + p/3)3 − [3(p2/9) − q]x − p3/27 + r = 0
(x + p/3)3 − [p2/3 − q]x − p3/27 + r = 0


Step 3:  Let x + p/3 = y then x = y − p/3.
Substitute y and (y − p/3) for (x + p/3) and x in the above equation.
y3 +[q − p2/3](y − p/3) + r − p3/27 = 0
y3 +[q − p2/3]y − [qp/3 − p3/9 − r + p3/27] = 0
y3 +[q − p2/3]y + [r − qp/3 + 2p3/27] = 0
y3 +[q − p2/3]y + [2p3/27 − qp/3 + r] = 0


Step 4: Now the equation is of the form y3 + Ay + B = 0
where A = q − p2/3 and B = 2p3/27 − qp/3 + r
Let y = (s − A/3s)
then s3 − A3/(3s)3 − As + A2/3s + As − A2/3s + B = 0
s3 − A3/(3s)3 + B = 0
Multiplying throughout by s3, we get
s6 + Bs3 − A3/27 = 0
Let, s3 = z
z2 + Bz − A3/27 = 0
z = [−B ±√(B2 + 4A3/27)]/2


s13 = [−B +√(B2 + 4A3/27)]/2
As we know that any equation has three cube roots. Let its cube root be s1. then the roots are s1, ωs1 and ω2s1.
Similarly,
s23 = [−B −√(B2 + 4A3/27)]/2
Let its cube root be s2. then the roots are s2, ωs2 and ω2s2.
1/s13 = −(3s2/A)3
⇒ 1/s13 = 1/[−B +√(B2 + 4A3/27)]/2
= {[−B − √(B2 + 4A3/27)]/2}/{[−B −√(B2 + 4A3/27)][−B +√(B2 + 4A3/27)]/4}
= {[−B − √(B2 + 4A3/27)]/2}/{−4A3/(27×4)}
= {[−B − √(B2 + 4A3/27)]/2}/{A3/27)}
= −(3s2/A)3
s1s2 = −A/3
If we consider s1 then −A/3s1 = s2.
The product of s1 and s2 is real so the possibilities of the roots for y (= s − A/3s) are
s1 + s2, (ωs1 + ω2s2) and (ω2s1 + ωs2).


Step 5: Shift the graph to the original position for the roots.
The three roots are
s1 + s2 − p/3, (ωs1 + ω2s2 − p/3) and (ω2s1 + ωs2 − p/3).

The solution of the equation
x3 + px2 + qx + r = 0 is
s1 + s2 − p/3, (ωs1 + ω2s2 − p/3) and (ω2s1 + ωs2 − p/3).

Where ω is a cube root of 1 i.e (−1 + i√3)/2
Where s1 is a cube root of [−B +√(B2 + 4A3/27)]/2 and
s2 is a cube root of [−B − √(B2 + 4A3/27)]/2.
and
where A = q − p2/3 and B = 2p3/27 − qp/3 + r

Saturday, August 23, 2014

How many Solutions of x + y + z = k

In this post we will consider all the positive integer solutions of the equation x + y + z = k. At the end of the post we will generalize the method.

Let us first solve the equation. There is a x, a y and a z. We can consider x 1's, y 1's and z 1's. So there are a total of (x + y + z) 1's. We can find its integer solutions by separating  1's at different positions. Consider the equation x + y + z = 9.

Some of the solutions of the equation are
11|111|1111 (2+3+4)
111|111|111 (3+3+3)
1111|111|11 (4+3+2)
1111|11|111 (4+2+3)
11|11|11111 (2+2+5)

Add all the ones in one group separated by |. The number of solutions of this type is the solution of the equation x + y + z = 9. The number of solutions of the equation is (9+2)!/(9!2!) = (11×10)/2 = 55. Hence there are 55 solutions. If we have the total as k and the number of plus sign is n. Then the total number of solutions is (k+n)!/(k!n!). This can be written in the combination symbol as C(n+k,k).

This equation is similar as taking the combination of r things in n containers of similar kind. The number of combinations is (n+r−1)!/(n−1)!r!. This can be written in the combination symbol as C(n+r−1,r).

Wednesday, August 20, 2014

Preliminaries in plane geometry (Part 2)

In this post we will discuss about equations of a line in different form. Every equation is related to other equation and can be derived from one other. In the post I have derived the different forms of equations of a straight line. I have started from an equation which is called two-point form and end with the normal form. normal form is also called perpendicular form. I have given graphs of four equations.

The equation of a line can be found if we know anyone of
  1. two points
  2. one point and slope of the line
  3. slope of the line and y intercept
  4. angle made by the perpendicular and its length to the line from the origin
The corresponding four types of equations are as follows
  1. two points form: (y−y1)/(x−x1) = (y2−y1)/(x2−x1)
  2. point-slope form: (y−y1) = m (x−x1)
  3. slope-intercept form: y = mx + c
  4. normal form: x cos α + y sin α = p

The four equations in the graph are
y = 3x + 4, y = x + 7 , y = 2x− 5 and y = −x + 3.

Let A(x1, y1) and B(x2, y2) be two points. Then the four types of equations can be framed as follows:
  1. As the slope of the line will be constant. So, if a variable point is (x,y) then
    (y−y1)/(x−x1) = (y2−y1)/(x2−x1)

  2. If the value of the slope is m then we can substitute,
    (y2−y1)/(x2−x1) = m
    and get the equation of the line as
    (y−y1)/(x−x1) = m
    (y−y1)= m (x−x1)

  3. Expanding (y−y1)=m(x−x1)
    y−y1= mx − mx1
    y = mx−(mx1− y1)
    As [−(mx1 − y1)] is a constant and can be substituted for c
    y = mx + c

    From the above equation we get y = c when x = 0. Hence, c is the y intercept.

  4. Normal form is found by considering the angle which the perpendicular from the origin  to the line makes with the x-axis and its length.

    In the figure the angle is α and the length of the perpendicular is p. Equation of line in two point form is
    (x1, y1) ≡ (a,0) and (x2, y2) ≡ (0,b)

    Using the two point form
    (y−y1)/(x−x1) = (y2−y1)/(x2−x1)
    y/(x − a) = b/(− a)
    −ay = bx − ab
    bx + ay = ab
    x/a + y/b = 1
    a = p sec α
    b = p cosec α
    x/(p sec α) + y/(p cosec α) = 1
    x cos α + y sin α = p

Tuesday, August 19, 2014

Preliminaries in plane geometry (Part 1)

Many shapes in a plane are well represented by equations. Circles, parabolas and hyperbolas are some of the shapes which can be represented by equations.
But to deal with them we need to know the basics of geometry. The posts related to basics of coordinate geometry is given in the related posts "Preliminaries in plane geometry". The posts will be given in many parts. each part will cover two to three topics. In this post we will discuss about Distance formula and Section formula.

Distance formula

The Cartesian coordinates are used to represent points in a plane. Every point in a place has a one to one relationship to a coordinate point. The distance (d)  between two points A(x1, y1) and B(x2, y2) is given by the formula
d = √[(x2 − x1)²+(y2 − y1)²]

The above formula can be found with the help of Pythagoras theorem. Draw a right angled triangle as shown in the graph. When we draw a right angled triangle we draw it such that the two edges including the right angle are parallel to the two axis. This helps us to find the coordinate of the vertex. Name the right angled vertex as C. The coordinate of the point C is (x2, y1). a line parallel to the coordinate axis has its other coordinate same. Suppose the line is parallel to x-axis then all the points on the line has its y-coordinate equal.  The distance between the points A and B is d. The distance between the points A and C is AC =(x2 − x1) and distance between the points B and C is BC =(y2 − y1). By Pythagoras Theorem we have (AB)² = (AC)² + (BC)². Substituting the value of AC and BC we get

d² = (x2 − x1)²+(y2 − y1
Taking square root and as distance cannot be negative, we get
d = √[(x2 − x1)²+(y2 − y1)²]

Example:
Distance between A(3,5) and B(1,2) is
AB = d
d = √[(1 − 3)²+(2 − 5)²]
= √(4+9)
= √13

Section Formula

A point C(x,y) is present between A(x1,y1) and B(x2,y2). C divides AB internally in the ratio m:n. Then the coordinate of C is given by

C≡( [mx2+nx1)/(m+n)] , [(my2+ny1)/(m+n)] )

Example:
C divides AB internally in the ratio 1:2. A(3,5) and B(1,2). Find C.
Let the coordinate of C be (x,y). Then
Here m=1, n=2, x1= 3, x2 = 1, y1 = 5, y2 = 2.
x = (1×1 + 2×3)/(2+1)
= 7/3
  y= (1×2 + 2×5)/(2+1)
= 12/3
= 4.
Hence the coordinate of C is (7/3,4).
If C divides AB externally in the ratio m:n. Then the coordinate of C is given by

C≡( [mx2− nx1)/(m − n)] , [(my2− ny1)/(m − n)] )


Example:
C divides AB externally in the ratio 2:1. A(3,5) and B(1,2). Find C.
Let the coordinate of C be (x,y). Then
Here m=2, n=1, x1= 3, x2 = 1, y1 = 5, y2 = 2.
x = (2×1 − 1×3)/(2 − 1)
= −1
  y = (2×2 − 1×5)/(2 − 1)
= −1
Hence the coordinate of C is (−1,−1).

Monday, August 18, 2014

Recurrence relation (Part 2) : Linear Equations

In the post Recurrence Relation (Part 1) we studied three examples of recurrence relations. In this post we will solve them. The recurrence relation (Tn = Tn-1 + Tn-2) of Fibonacci problem is linear and has order 2 and degree 1. It is also homogeneous. The recurrence relation (Tn = 2Tn-1 + 1) of Tower of Hanoi problem is also linear. It has order 1 and degree 1 but it is non homogeneous. Recurrence relations can exist in many forms as linear or non-linear.

A linear recurrence relation looks like this

Tn = f1(n)Tn-1 + f2(n)Tn-2 + f3(n)Tn-3 + ...+ fr(n)Tn-r+...+fn-1(n)T1 + f(n)

The order of the recurrence relation is r if fi(n) = 0 for i > r.
It is called homogeneous if f(n) = 0 and non-homogeneous if f(n) ≠ 0.
We will consider linear homogeneous and non-homogeneous recurrence relation with constant coefficients. A linear recurrence relation with constant coefficients is given by

Tn = C1Tn-1 + C2Tn-2 + C3Tn-3 + ...+ CrTn-r+...+Cn-1T1 + f(n)
 
where Ci is a constant, 0 < i < n.
The order of the recurrence relation is r if Ci = 0 for i > r.
It is called homogeneous if f(n) = 0 and non-homogeneous if f(n) ≠ 0.


We will solve the linear homogeneous recurrence relation with constant coefficients first. The example of this type of equation which we are going to solve is Fibonacci Problem.
Tn = Tn−1 + Tn−2

Substitute the Terms with the r(the subscript)
We get,
rn = rn−1 + rn−2
Divide throughout by the lowest power term which is rn-2.
We get,
r2 = r + 1
r2 − r − 1 = 0
The above equation is called the characteristic polynomial of the recurrence relation and its roots are called characteristic roots.
The solution of the polynomial is r1 = (1 + √5)/2 and r2 = (1 − √5)/2

The solution of the recurrence relation can be written like this
Tn = A(r1)n + B(r2)n = A[(1 + √5)/2]n + B[(1 − √5)/2]n

T1 = 1 = A[(1 + √5)/2] + B[(1 − √5)/2] = (A + B)/2 + (√5)/2(A − B)
T2 = 1 = A[(1 + √5)/2]2 + B[(1 − √5)/2]2
= A [1 + 5 + 2√5]/4 + B [1 + 5 − 2√5]/4
= A [6 + 2√5]/4 + B[6 − 2√5]/4

We get two relations
(A + B) + (√5)(A − B) = 2 ----(i)
and
3(A + B) + (√5)(A − B) = 2 ----(ii)

Solving the equations simultaneously, we get
3(i) - (ii)
2√5(A − B) = 4
A − B = 2/√5 and substituting in (i)  we get
A + B = 0

Again solving simultaneously,
2A = 2/√5
A = 1/√5
B = -1/√5
Hence the solution of the recurrence is
Tn = [1/√5][(1 + √5)/2]n - [1/√5][(1 − √5)/2]n


Next we will solve the recurrence relation Tn = 2Tn−1 + 1 which belongs to the tower of Hanoi problem.

Linear non homogeneous recurrences require us to solve for their homogeneous part then substitute a relation which satisfies the non homogeneous recurrence. There are many methods which are different from it and can be used to solve many recurrences. These methods are
  1. Method of iteration
  2. Method of substitution
  3. Method of telescoping sums
  4. Method of inspection
Here, we will use method of iteration to solve the recurrence.
In this method we substitute the earlier term in the recurrence and look at the pattern and solve the series.
Tn = 2Tn−1 + 1
Tn = 2(2Tn−2 + 1) + 1
Tn = 2(2(2Tn−3 + 1) + 1) + 1
As T1 = 1, so we get
Tn = 2n-1 + 1 + 2 + 22 +....+ 2n-2
Tn = 2n-1 + (2n-1 − 1) = 2n − 1

Now we will solve the recurrence Tn = Tn-1 + k. This problem is multiplication problem. This recurrence will be solved by inspection. In inspection we write down enough terms such that we can guess the solution.
T1 = k. Hence,
Tn  = Tn−2 + k + k
Tn  = Tn−3 + k + k + k
Tn  = Tn−4 + k + k + k + k
We can guess the solution to be Tn = nk as the number of k's increases as we use the lower terms of the recurrence and it increases by a definite number..

Sunday, August 17, 2014

Whether real or complex (Cubic Equation)

This post deal with the conditions to check whether the roots are real or complex of a cubic equation. A cubic equation always has a real root. The other two roots are real or complex according as the graph cuts the x axis in one or three positions. If the graph touches the x-axis then two roots are equal. If the graph cuts the x-axis in three positions then all the roots are real. If the graph cuts the x-axis in one position then other two roots are complex. When we look at the graph of a general cubic equation we see a cup like structure and a cap like structure. The base of the cup like structure gives local minima and the top of cap like structure gives local maxima. Let us find the positions where the curve bends and changes its direction. We call the cup like structure concave upward and a cap like structure convex upward. The quadratic equation is ax3 + bx2 + cx + d = 0. Let it be equal to y or f(x). y = ax3 + bx2 + cx + d. Now the rate of change of curve is f '(x) = 3ax2 + 2bx + c. f(x) is differentiated to obtain f '(x). We again differentiate f '(x) to obtain f ''(x),

f ''(x) = 6ax + 2b
f ''(x) = 6a(x + b/3a)

Let us check, for what values of x it may give maxima and for what values it may give minima.
There are four cases for it and is given in the following table

f ''(x)xastate
> 0x < (−b/3a)a < 0minima
< 0x > (−b/3a)a < 0maxima
< 0x < (−b/3a)a > 0maxima
> 0x > (−b/3a)a > 0minima

When the local maxima and and local minima are on opposite sides of x-axis then all the roots are real.

Let us find the x-coordinate of maxima or minima. It is when f '(x)=0.

Solving 3ax2 + 2bx + c = 0 we get
x = [−2b±√(4b2 − 12ac)]/6a
x = [−b±√(b2 − 3ac)]/3a
or
x1 = [−b+√(b2 − 3ac)]/3a
and
x2 = [−b−√(b2 − 3ac)]/3a
 
Find the value of y for x1 and x2, substituting them in place of x.

For x1 we get y1 = [4b3 − 15abc + 27a2d + (6ac − 2b2)√(b2 −3ac)]/27a2

For x2 we get y2 = [4b3 − 15abc + 27a2d − (6ac − 2b2)√(b2 −3ac)]/27a2

Now local maxima and local minima lie on the opposite sides of the x-axis when y1 and y2 lie on the opposite sides of x-axis. This will happen when they are of opposite sign.

Now four cases arise:
y1y2Remark
y1< 0y2< 0One root is real and other two are complex.
Graph of  y = x3 + 4x2 + 4x − 7
y1< 0y2> 0All the three roots are real.
 Graph of y = x3 + 6x2 + 4x − 7
If y1 = 0 or y2 = 0 then there are two equal roots
and it may be
  [−b+√(b2 − 3ac)]/3a or [−b-√(b2 − 3ac)]/3a
y1> 0y2< 0All the three roots are real.
Graph of y = − x3 + 4x2 + 4x − 7
If y1 = 0 or y2 = 0 then there are two equal roots.
and it may be
  [−b+√(b2 − 3ac)]/3a or [−b-√(b2 − 3ac)]/3a
y1> 0y2> 0One root is real and other two are complex.
Graph of y = x3 + 4x2 + 4x + 7

When (b2 − 3ac) is less than zero then y1 and y2 are complex and there is no maxima and minima. Then the equation has only one real root and other two are complex. See the graph for 3x2 + 2x2 + 3x + 4 = 0.
Where (b2 − 3ac) = (4 − 27) < 0.



When y1 or y2 is equal to zero then there are two equal roots.

Wednesday, August 13, 2014

Recurrence Relation (Part 1)

In mathematics we come across many series which can be expressed in terms of its some or every term. These terms can be distributed in the whole of the series. For example if the nth term is termed as Tn and it depends on its previous two terms then Tn can be expressed as many recurrence relation with these two terms. One of it is Tn = Tn-1 + Tn-2. Recurrence relations are used in computer science to find the time complexity of many algorithms. Let us consider some examples of recurrence relations. We will solve them in some other post.

  • Multiple by consecutive numbers: Look at the series 2,4,6,8,10,12,14,16...The series can be represented as 0+2, 2+2, 4+2, 6+2, 8+2, 10+2, 12+2, 14+2...Here every term can be represented as sum of the previous term and 2.Hence, multiplication of 2 and consecutive natural numbers can be represented like this. Tn = Tn−1 + 2 where the first term is T1 = 2. Similarly, multiplication of can be represented like Tn = Tn−1 + k where T1 = k.


  • Fibonacci Series: Leonardo di Pisa also known as Fibonacci posed a problem about rabbits in his book Liber Abaci in 1202. The problem stated: One pair of rabbits, one male and one female, are left on an island. These rabbits begin breeding at the end of two months and produce a pair of rabbits of opposite sex at the end of each month thereafter. Can you determine the number of pairs of rabbits after n months assuming no rabbit dies on this island?

    Let us try to solve this problem. In first month there is one pair. So, T1 = 1. In the second month there is one pair. So, T2 = 1. In the third month there are two pairs. So, T3 = 2. Two are the rabbits in the first month and additional two are due to birth. In fourth month the pair of children produced are equal to the pairs of rabbits in the second month which can produce, this is equal to 1. The additional number of pairs are those in third month which equals 2. So, T4 = 3. So it can be expressed in the recurrence relation as Tn = Tn-1 + Tn-2. Where Tn, Tn-1 and Tn-2 is pair of rabbits in nth, n-1th and n-2th month respectively.

  • The tower of Hanoi: The problem is invented by Edouard Lucas in 1883. We are given a tower of eight discs, initially stacked in decreasing size on one of three pegs. The problem is to transfer the entire tower to one of three pegs, moving only one disc at a time without ever moving a larger disc onto a smaller one.

    Let us solve this problem.

    1. With one disk we can move it in 1 move. So T1 = 1.
    2. With two disks we can move it in 3 moves. The procedure is like this. There are three pegs A, B and C. A has both the disks in increasing order from top arranged in the order 2,1. We move 1 to B. Then move 2 to C. Then move 1 to C. So the number of moves for two disks is three. So, T2 = 3.
    3. For three disks, we can move it in 7 moves. The procedure is like this. There are three pegs A, B and C. A has all the three disks in increasing order from top arranged in the order 3,2,1. We, move 1 to C, move 2 to B, move 1 to B, move 3 to C, move 1 to A. Then move 2 to C. Then move 1 to C. So the number of moves for three disks is seven. So, T3 = 7.
    We can generalize the procedure like this, move n−1 disks to one peg then move the nth disk and bring back the n−1 disks above the nth disk. We can solve this problem in Tn = 2Tn-1 + 1 moves.
Read solutions of the above recurrences