Mathematical Induction:

The need for proof:

Most of the people nowadays are lazy. We watch too much television and are content to accept the things as true with no question.

When we see something which works a few times in a row, we are convinced that this works forever.

Regions of a Circle:

Let consider a circle with n points on it. How many regions will the circle are divided into when each and every pair of points is joined with a chord?

At this point, most likely everyone would be persuaded that with 6 points there would be 32 regions, but it is not proved, it is just conjectured. The conjecture is that number of regions when n points are joined is 2^n-1.

Will finding out the number of regions if there are six points on the circle, prove the conjecture? No. When there are indeed 32 regions, all you have done is shown the other illustration to support your conjecture. When there are not 32 regions, then you have proved the conjecture wrong. However, when you go ahead and try the circle with six points on it, we will find out that there are not 32 regions.

We can never demonstrate a conjecture is true by illustration.

We can prove a conjecture is false by finding out a counter-illustration.

To prove a conjecture is accurate, you require some more formal techniques of proof. One of such methods is the principle of the mathematical induction.

Principle of Mathematical Induction (English):

a) Illustrate something works the first time.
b) Suppose that it works for this time.
c) Show it will work for subsequent time.
d) Conclusion, this works all the time.

Principle of Mathematical Induction (Mathematics):

a) It show true for n = 1
b) Suppose true for n = k
c) It show true for n = k + 1
d) Conclusion: Statement is true for all the n >= 1

The keyword in step b is assumed. You are not trying to prove it is true for n = k, you are going to admit on faith that it is, and illustrate it is true for next number, n = k + 1. When it later turns out that you obtain a contradiction, then the supposition was wrong.

Annotated illustration of Mathematical Induction:

Prove 1 + 4 + 9 + ... + n2 = n (n + 1) (2n + 1)/6 for all positive integers n:

The other way to write ‘for each and every positive integer n’ is for each and every positive integer n. This works since Z is the set of integers, therefore Z+ is the set of positive integers. The upside down A is symbol for ‘for all’ or ‘for every’ or ‘for each’ and the symbol which looks similar to a weird e is the ‘element of’ symbol. Therefore technically, the statement is stating ‘for each and every n which is an element of the positive integers’, however it is simpler to state ‘for each and every positive integer n’.

Identify the general term and nth partial sum before starting the problem:

The general term, a_n, is the last term on the left hand side. a_n = n²

The nth partial sum S_n, is the right hand side. S_n = n (n + 1) (2n + 1)/6

Find the next term in general sequence and the series:

The next term in the sequence is ak+1 and is found by substituting n with k+1 in the general term of sequence, a_n.
a_k+1 = (k + 1)²

Next term in the series is S_k+1 and is found by substituting n with k+1 in nth partial sum, S_n. You might wish to simplify the next partial sum, S_k+1

S_k+1 = (k+1) [(k+1) + 1] [2(k+1) + 1] / 6
S_k+1 = (k + 1) (k + 2) (2k +3)/6 (This will be our aim in step 3)

We will use such definitions later in the mathematical induction procedure. We are now ready to start.

A) Illustrate the statement is true for n = 1, that is, illustrate that a₁ = S₁.
a₁ is the first term on left or you can determine it by replacing n = 1 to the formula for the general term, a_n.

S₁ is found by replacing n = 1 to the formula for nth partial sum, S_n.

lhs: a₁ = 1

rhs: S₁ = 1 (1+1) [2(1) + 1]/6 = 1(2)(3)/6 = 1

Therefore, we can see that the left hand side equivalents the right hand side for the first term, therefore we have established the primary condition of mathematical induction.

B) Suppose the statement is true for n = k

The left hand side is the sum of first k terms, therefore we can write that as Sk. The right hand side is determined by replacing n = k to the S_n formula.

Suppose that S_k = k (k + 1) (2k + 1)/6

C) Exhibit the statement is true for n = k+1:

What we are trying to illustrate is that S_k+1 = (k + 1) (k + 2) (2k +3)/6. This was main goal from former.

We start with something that we know (suppose) is true and add up the next term, a_k+1, to both the sides.

S_k + a_k+1 = k (k + 1) (2k + 1)/6 + a_k+1

On left hand side, S_k + a_k+1 signifies the ‘sum of the first k terms’ plus ‘the k+1 term’, that gives us the sum of first k+1 terms, S_k+1.

This frequently gives students problems; therefore let’s think about it this manner. Suppose k = 10. Then S_k would be S₁₀, the sum of first 10 terms and a_k+1 would be a11, the 11th term in the sequence. S₁₀ + a₁₁ would be the sum of 10 terms plus the 11th term that would be the sum of first 11 terms.

On the right hand side, substitute a_k+1 by (k+1)², that is what you determined it was before starting the problem.

S_k+1 = k (k + 1) (2k + 1)/6 + (k + 1)²

Now, try to turn your right hand side to the goal of (k + 1) (k + 2) (2k +3)/6.

You require getting a common denominator; therefore multiply the last term by 6/6.

S_k+1 = k (k + 1) (2k + 1)/6 + 6 (k + 1)2/6

Now simplify it. This is almost always simpler to factor instead of expand whenever simplifying. This is particularly aided by the fact that your aim is in factored form. We can use that to help you factor. We know that you wish a (k+1) (k+2) (2k+3) in final form. We observe right now that there is a (k+1) which is common to both of such; therefore let us start by factoring it out.

S_k+1 = (k + 1) [k (2k + 1) + 6 (k + 1)]/6

What is left within the brackets [ ] does not factor, therefore we expand and join like terms.

S_k+1 = (k + 1) (2k² + k + 6k + 6)/6

S_k+1 = (k + 1) (2k² + 7k + 6)/6

Now, try to factor 2k² + 7k + 6, keeping in mind that you require a (k+2) and (2k+3) in the goal which you do not have yet.

S_k+1 = (k + 1) (k + 2) (2k + 3)/6

Conclusion:

The conclusion is determined by stating ‘Therefore, by the principle of mathematical induction’ and restating the original claim.

Thus by the principle of mathematical induction:

1 + 4 + 9 + ... + n² = n (n + 1) (2n + 1)/6 for all the positive integers n.

Summations:

In the given illustrations, c is a constant and x and y is functions of index.

We can factor a constant out of the summation:

∑cx = c∑x

Sum of a constant time a function is the constant times the sum of function.

The sum of a sum is the sum of sums:

∑(x+y) = ∑x + ∑y

The summation sign can distribute over the addition.

The sum of a difference is the difference of the sums:

∑(x-y) = ∑x - ∑y

The summation sign can distribute over the subtraction.

Sum of the Powers of the Integers:

Now, we are going to look at the sum of whole number powers of natural numbers.
 
The closed form for the summation is a formula which permits you to determine the sum simply by recognizing the number of terms.

Finding Closed Form:

Determine the sum of: 1 + 8 + 22 + 42 + ... + (3n²-n-2)

The common term is an = 3n²-n-2, so what we are trying to determine is ∑(3k²-k-2), where ∑ is really the sum from k = 1 to n.

Take the original, open form of summation, ∑(3k²-k-2)

Allocate the summation sign, ∑3k² - ∑k - ∑2

Factor out some constants, 3∑k² - ∑k - 2∑1

Substitute each and every summation by the closed form shown above. Closed form is a formula for the sum which does not comprise the summation sign, just n.

3[n(n+1)(2n+1)/6] - [n(n+1)/2] - 2[n]

Now, get a common denominator, here in this case, 2.

n(n+1)(2n+1)/2 - n(n+1)/2-4n/2

Keep in mind that the word factor starts with the letter F and anytime you have an option of doing something in mathematics which begins with the letter F that is probably where you should begin. Therefore, do not expand, factor rather.

The common factor is n therefore we will factor that out of each term. The entire expression is over 2.

n [ (n+1)(2n+1) - (n+1) - 4 ] / 2

Now expand within the brackets [ ].

n [2n² + 3n + 1 - n - 1 - 4 ] / 2

Simplify like terms.

n (2n² + 2n - 4 )/2

Notice that the common factor of 2 within the parentheses let us factor that out.

2 n (n² + n - 2) / 2

The 2 in the numerator and 2 in denominator divide out and we can factor the rest to obtain the closed form for sum.

n ( n + 2 ) ( n - 1)

Prove:

We are not going to prove that statement, however that is how many books came up with most of the problems that you are asked to prove. You take an open form, determine the closed form, and then put it in text as a problem for the student to prove.

Pattern Recognition:

At times you have to figure out what general term of a sequence is. Here are few guidelines.

a) Compute the first some terms of the sequence. At times it aids to write the term in factored and expanded form.

b) Try to determine a recognizable pattern. Here are few things to look for:

•    Linear patterns: an + b (will encompass a common difference)
•    Quadratic pattern: an² + b (that is the perfect squares plus or minus a constant)
•    Cubic pattern: an³ + b (that is, the perfect cubes plus or minus a constant)
•    Exponential patterns: 2n + b, 3n + b (that is, the powers of 2 or 3 plus or minus a constant)
•    Factorial patterns: n!, (2n)!, (2n-1)! (Factoring such really helps).

c) After you have your pattern, then you can utilize mathematical induction to prove the conjecture is accurate.

Finite Differences:

The Finite differences can help you to determine the pattern when you have a polynomial sequence.

The first differences are determined by subtracting the consecutive terms. When the first differences are all similar, then the pattern is linear.

The second differences are determined by subtracting the consecutive first differences. When the second differences are all similar, then the pattern is quadratic. Keep in mind that you can determine a quadratic model by taking the equation y = ax² + bx + c with three points. Then resolve the system of equations which results. The analogy here is that you can find out an = an² + bn + c by replacing in three terms in the sequence and their corresponding place in the sequence for n. Then resolve the system of linear equations.

This can be extended to the third differences by subtracting the consecutive second differences. When the third differences are all similar, then the pattern is cubic. We can fit a cubic model with four points and the model an = an³+bn²+cn+d.

Finite Differences illustration:

Find out the general term of the sequence 1, -2, -1, 4, 13, 26, 43, 64, 89....

The first finite differences are determined by subtracting the consecutive terms in original sequence. That is, take -2-1=-3, -1-(-2)=1, 4-(-1)=5, 13-4=9, 26-13=13, and so on.

The first finite differences are: -3, 1, 5, 9, 13, 17, 21, 25....

As these are not all similar, your sequence is not linear (that is, first degree) polynomial.

Move on to second finite differences. Such are the differences in consecutive terms of the first finite differences. 1-(-3)=4, 5-1=4, 9-5=4, 13-9=4, 17-13=4 and so on.

The second finite differences are: 4, 4, 4, 4, 4, 4, 4....

As the second finite differences are the entire similar, your sequence is that of second degree polynomial and you can write the general term as: an = An² + Bn + C.

Plug in the values 1, 2, 3 (as there are three variables) to the expression.

i) If n = 1, 1A + 1B + 1C = 1 (that is, first term is 1)
ii) If n = 2, 4A + 2B + 1C = -2 (that is, second term is -2)
iii) If n = 3, 9A + 3B + 1C = -1 (that is, third term is -1)

Now, solve that system of linear equations (it is recommend to use matrix inverses AX = B, therefore X=A^-1B).

In our condition, we get A = 2, B = -9, and C = 8, therefore the general term of our sequence is an = 2n²-9n+8.

If we wish to check it, pick any value for n and plug it to the general term. We must get the nth number in sequence. For illustration, if n = 6, then a⁶ = 2(6)² - 9(6) + 8 = 26. Check the sequence, sure adequate, the 6th number is 26.

Latest technology based Algebra Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Algebra help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Algebra, project ideas and tutorials. We provide email based Algebra help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Algebra. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Algebra Homework help and assignment help services. They use their experience, as they have solved thousands of the Algebra assignments, which may help you to solve your complex issues of Algebra. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.