# Principle of Mathematical Induction

Extrapolating generalizations from fixed results is known as induction. Principle of Mathematical Induction is a generalisation of this used to prove any mathematical claim.

For any natural number, say N, the mathematical induction is a strategy for proving a statement, theorem, or formula which is assumed to be true. To prove that the establishing statement or result are formulated in terms of n, where n is a natural number, we follow steps, P(n) as mentioned below:

1. The statement is considered to be true for n = 1, P(1) is true.
2. If the statement is considered to be true for n = k, where k is some positive integer, P(k) is true.
3. Prove that the result is also true for P(k+1) for any positive integer k.

If all these conditions are fulfilled, then P(n) is true for all natural numbers.

## Proof

The first step in this principle where we take the trivial case is known as the factual statement. In the second step, we take a condition therefore it is called the conditional step. According to the steps mentioned above, then if the given assertion is true only for some positive integer k, then P(n) is true for n = k+1. The assumption taken at P(n) is valid for n = k is called the inductive hypothesis. Now we take a simple example to prove the hypothesis. We have to prove that the sum of first n odd numbers is the square of n.

1 + 3 + 5 + 7 + … + (2n-1) = n².

P(n): 1 + 3 + 5 + 7 + …+ (2n-1) =  n².

We have to prove that P(n) is true for all n

Following the steps above,

We prove that P(1) is true. This is called the basic step.

1 =  1² which implies that P(1) is true.

Now, we suppose that P(k) is true for some positive integer k. Since P(k) is true, we have

1 + 3 + 5 + 7 + … + (2k-1) =  k²

Now we need to prove that P(k+1  is true.

1 + 3 + 5 + 7 + … + (2k-1) =  k²    —(1)

Consider

1 + 3 + 5 +  7 + … + (2k-1) + {2(k+1) – 1}    —(2)

=   k² + (2k + 1) =   (k+1)²       [when using (1)]

For that reason, P (k +1) is true along with the inductive proof, which is now completed.

Therefore, P(n) is true for all of the natural numbers n.

## History of Principle of Mathematical Induction

Proof by mathematical induction, unlike other concepts and procedures, is not the creation of a single person at a specific time. The Pythagoreans are considered to have understood the principle of mathematical induction. The mathematical induction concept is credited to the French mathematician Blaise Pascal. JohnWallis, an English mathematician, coined the term induction. Later, the idea was used to demonstrate the binomial theorem. DeMorgan made numerous contributions to the discipline of mathematics on a variety of topics. He was the first to define and identify “mathematical induction,” as well as construct De Morgan’s rule for determining a mathematical series’ convergence. G Peano set out to deduce the properties of natural numbers from a series of explicit assumptions, which became known as Peano’s axioms. The mathematical induction principle is a statement of one of Peano’s axioms.

## Solved Examples

### Example1

For all n ≥ 1, we have to prove that

1² + 2² + 3² + 4² + … n² = n(n+1)(2n+1)/6

Solution

Let the given statement become P(n), i.e.,

P(n) :1²  + 2² + 3² + 4² + … n² = n(n+1)(2n+1)/6

For, say n = 1

Therefore, P(1): 1 =1(1+1)(2.1+1)/6 which is true.

Now, assume that P(k) is true for some positive integer k, i.e.,

1²  + 2² + 3² + 4² + … k² = k(k+1)(2k+1)/6      —(1)

We shall now prove that P(k + 1) is also true. Now, we have

(1²  + 2² + 3² + 4² + … + k² ) + (k+1)²

k(k+1)(2k+1)6 + (k+1)²        [when using(1)]

The equation becomes k(k+1)(2k+1)+6(k+1)²/6

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

(k+1)(k+1+1){2(k+1)+1}/6

Thus P(k + 1) is true, whenever P (k) is true.

Hence, from the principle of mathematical induction, the statement P(n) is true for all natural numbers n.

Example2

For every positive integer n, we have t prove that  7n –  3n  is divisible by 4.

Solution

We write P(n) :  7n –  3n, that is divisible by 4.

We need to note that P(1):  71 –  31 = 4, which seems to be divisible by 4. Consequently P(n) becomes true for n = 1.

Now, lets assume that P(k) is true for some natural number k,

i.e., P(k) :  7k –  3k is divisible by 4.

We can write  7k –  3k = 4d, where d ∈ N.

Now, we need to prove that P(k + 1) is true at any moment P(k) is true.

Now 7(k+1) –  3(k+1) = 7(k+1) –  7.3k + 7.3k –  3(k+1)

= 7(7k –  3k) + (7-3) 3k

= 7(4d) + (7-3)3k

= 7(4d) + 4. 3k

= 4(7d + 3k)

From the last line, we get to see that 7(k+1) –  3(k+1) is divisible truly by 4. Therefore, P(k + 1) is true whenever P(k) is true. So, by using the principle of mathematical induction the statement is true for every positive integer n.

### Conclusion

Here, we learned about the Principle of Mathematical Induction. It is defined as a method, which is used to establish results for the natural numbers. In simple terms, we can say that this method is used to prove if the statement or theorem is found to be true for all natural numbers. The proof involves two cases. We first prove the statement for n = 1, this step is called the base case. In the next step, called the induction step, we check if the statement holds for any given case n=k, then it must also hold for the next case n=k+1.

n stands for the gross quantity of components in a bunch.

k stands for the number of selected issues (as the order of the objects is not essential)

! indicates factorial.

Factorial (noted as “!”) is a property of all optimistic numerals insufficient or comparable to the amount preceding the factorial evidence. For instance, 3! = 1 x 2 x 3 = 6.

Note that the formula above can be employed barely when the objects from a pair are appointed without reproduction.

#### Example of Combination

The following is about a manager’s portfolio in a minor hedge fund. The manager is supposed to develop a new fund to prevent risk-taking investors. The fund perhaps includes commodities of rapidly-growing firms offering increased outgrown capabilities. The analytic team specified the stock of closely 20 companies according to their profile. The manager further involved five additional supplies and proportional weight in the primary portfolio. It is just because the fund is new. At present, the manager desires to identify several probable portfolios. It will help him develop from those stocks identified by the analyst team.

It is a decision-making process in investment and the above example is about a combination problem. Since an individual will create a portfolio in which the entire stocks will be of the same weights. The order of the chosen stores will not affect the portfolio. For instance, the portfolio ABC and CBA will remain the same for each stock because of the same way.

### Definition of Permutation and Combination

Instead, it is essential to understand permutation and combination better and the relationship and differences between them.

Most of the possibilities of mathematical permutation happen. In premutation, an individual arranges a data pair in a specific order or sequence. However, if the data is ultimately set in order, the individual has the power to rearrange them. In such cases, the individual will use the permutation formula. On the other hand, a combination for another, contrary to premutation, is when an individual selects data from a year without any order or even sequences. If the data group is comparatively lesser, an individual can measure the number of probable combinations. This definition is elaborated below with potential permutation and combination search examples.

For instance, an individual has a group of four letters P, Q, R, S. Now, and there are different ways an individual selects three letters from this group. Every possible arrangement can be a combination.

### Permutation Formula

If the entire amount of data is “n” and the selection is of “r” things, accordingly permutation will be without alternate and respecting an order of

### Conclusion

A combination is barely a way of appointing some objects from a provided pair of things in a specific way that the order of their choice doesn’t matter. Moreover, it is determined that one is not assigning a sole commodity further once, i.e. reduplication is not permitted. On the other hand, it is a combination. The order of objects is affordable. It is only the preference of valuable things, not its configuration with appreciation to other appointed entities.

Get answers to the most common queries related to the CA Foundation Examination Preparation.

## What does combination mean in mathematics?

Ans. In mathematics, a combination is a choice of commodities from a bunch wit...Read full

## Can you give an example of combinations?

Ans. A combination is a choice of a total or portion of a pair of matters without concern to the order in which obje...Read full

## How do you solve combinations in math?

Ans. Evaluating varieties, an individual will exert the Combination ...Read full

## How many types of combinations are there?

Ans. There are three main categories of a combination reaction...Read full

## What are combination reactions and examples?

Ans. When more than two reactants combine to form a new product, it is called ...Read full