Proofs by Induction

Motivating the application of the method by looking at natural numbers as the least inductive subset of real numbers.

Proofs by Induction

In this section, we’ll be learning about the mathematical induction which proves that a specific statement holds true for all the integers that are positive.

Now, first let’s make a rough guess at the formula, giving us the sum of all positive integers, ranging from 1 to n for any value of the integer “n”. From the Gauss’s formula, you can conclude in a general form that if there are 100 numbers, then there’ll be 50 pairs. So, if n numbers will be in action, then, (n/2) pairs will be out there.

1 and 100 were the first and endmost numbers. And together when they are added results in the sum of 101. 101 number was sum of each of the pairs in their total sum. Thus, we may speculate that sum of first “n” positive integers results in n((1 +n)/2).

Although, this formula operates for all the “n” positive integers.

Summarized Induction’s Idea:

Assuming the statement holds true for – a few of the arbitrary n values, and in addition, shows that if statement for n = k is true, then it must be true for the value n = k+1, also.

The above process is in use as you can’t actually predict or prove to them that it holds true and precise for each of the values. Let’s say, n = 500, then n = 501, and then n = 502, however then can you answer, what’ll be about the numbers 503? 504? 1000?, a million, a trillion?

The Mathematical Induction let’s you to prove a statement whose existence is true in basic 3 steps:

Step 1: Base Case

To prove that statement is true or in a way correct for n’s first value. Considering some of the cases, this may result as, n = 0.

In the case of the formula for sum of integers, given above, we would be starting with the value, n = 1.

Often concerning induction, you might be wanting to extend step I so as to show that a statement holds true for various n values.

Step 2: Inductive Hypothesis

Supposing that a statement does holds true n’s kth value. In the condition regarding the formula for sum the integers, we will be stating the following that – first ‘k’ positive integers’s sum is k((1 + k)/2).

Step 3: Inductive Step

Make use of inductive hypothesis for representing that a statement holds true for k+1 step. In this case pointing out “integer sum formula”, we’ll be verifying-

Let us take the sum of the 1st k integers which are positive i.e. is k((1 + k)/2), and the sum of 1st k +1 positive integers = ((k + 1) (1 + (k + 1)/2).

Carrying out this kind of proof requires that you perform each of these steps., For the third step in particular you must rely on your algebra skills.

Let n = k + 1.
Then 1 + 2 + 3 + 4 + … + k + (k + 1)	[the left-hand side of (*)]
= [1 + 2 + 3 + 4 + … + k] + k + 1	[from part three]
= [(k)(k+1)/2] + k + 1	[our assumption]
= [(k)(k+1)/2] + 2(k+1)/2	[common denominator]
= (k)(k+1)+2(k+1)/2	[adding fractions]
= (k+2)(k+1)/2	[simplifying]
= ((k+1)+1)(k+1)/2	[restating in “k + 1″ form]

Conclusion

Hence, bringing this very proof type needs that you must follow each of these steps which are mentioned above.

Note: For the 3rd step specifically, you should be relying on the algebra skills of yours.