Principle Of Mathematical Induction Problems

There are some results or statements in algebra which are formulated in terms of n, where n is a positive integer. We use the principle of mathematical induction to prove such statements. In this article we come across Principle Of Mathematical Induction Problems. 

Mathematical Induction involves the composition of results or statements. In common, it is used for the set of natural numbers. The statement needs to be proven is termed as a deduction. For example, in the dominoes, if the first domino is knocked, it falls. If any domino is knocked, then the one next to it will also fall.

Formal Definition:

The mathematical induction principle states that a property holds good for all natural numbers from 0 to n. Consider a given statement, say P(n) consisting natural number n, such that

  • The given statement is correct for n = 1, the first natural number, then X(1) is true.
  • If the given result is true for any natural number, say k, then it will be valid for n = k + 1, also if X (k) is true, then X (k + 1) is also true.

If the above two steps are satisfied for P(n) natural numbers, then the principle of mathematical induction is valid.

  • In some instances, the statement is true for the results n ≥ 7, then the steps will start from n = 7 and hence check the result for n = 7 and so on.
  • The second property given in the principle of mathematical induction is conditional. It doesn’t confirm that the statement is valid for n = k but if it holds good for n = k, then it is true for n = k + 1 also.

The given statement is true for n=k is a presumption and hence called the hypothesis of induction.

Also read Limits Continuity And Differentiability

Solved Problems on Principle of Mathematical Induction for IIT JEE

Example 1: Prove that 3n>n for all positive integers n.

Solution:

Let P(n) = 3n>n

Put n = 1.

⇒ P(1) = 31>1.

So P(1) is true.

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

3k>k  …(1)

Now we prove that P(k+1) is true whenever P(k) is true.

Multiply both sides of (1) by 3

3.3k> 3k

⇒ 3k+1 > k+k+k > k+1

∴ P(k+1) is true when p(k) is true. 

Hence by mathematical induction principle, P(n) is true for every positive integer n

Example 2: Find the sum to n natural numbers through mathematical induction.

Solution: 

1+2+3+Findthesequencefortheterms1,2,3:arithmeticsequence:d=1,an=nArithmeticsequencesumformula:n(a1+d(n1)2)=n(1+1(n1)2)=n(n12+1)1+n12=122+n12=12+n12=n+12nn+12=(n+1)n2=n(n+1)21+2+3+\ldots \:\\\mathrm{Find\:the\:sequence\:for\:the\:terms\:}1,\:2,\:3:\quad \mathrm{arithmetic\:sequence}:d=1,\:a_n=n\\\mathrm{Arithmetic\:sequence\:sum\:formula:}\\n\left(a_1+\frac{d\left(n-1\right)}{2}\right)\\=n\left(1+\frac{1\cdot \left(n-1\right)}{2}\right)\\=n\left(\frac{n-1}{2}+1\right)\\1+\frac{n-1}{2}\\=\frac{1\cdot \:2}{2}+\frac{n-1}{2}\\=\frac{1\cdot \:2+n-1}{2}\\=\frac{n+1}{2}\\\Rightarrow n\frac{n+1}{2}\\=\frac{\left(n+1\right)n}{2}\\=\frac{n\left(n+1\right)}{2}\\

Example 3: Prove using mathematical induction that n=1nn2=n(n+1)(2n+1)6\sum _{n=1}^nn^2=\frac{n\left(n+1\right)\left(2n+1\right)}{6} is true for all positive integers n.

Solution:

Checkforn=1Letn=112=1(1+1)(21+1)6=66=11=1TrueInductionhypothesis:Assumethatn=nholdsn=1nn2=n(n+1)(2n+1)6(n+1)=1n+1(n+1)2=(n+1)((n+1)+1)(2(n+1)+1)6(n+1)=1n+1(n+1)2=(n+1)2+n=1nn2Byinductionhypothesisn=1nn2=n(n+1)(2n+1)6\mathrm{Check\:for\:}n=1\\\mathrm{Let\:}n=1\\1^2=\frac{1\cdot \left(1+1\right)\left(2\cdot \:1+1\right)}{6}\\=\frac{6}{6}\\=1\\1=1\\\mathrm{True}\\\mathrm{Induction\:hypothesis:\:\:\mathrm{\:}Assume\:that\:}n=n\mathrm{\:holds}\\\sum _{n=1}^nn^2=\frac{n\left(n+1\right)\left(2n+1\right)}{6}\\\sum _{\left(n+1\right)=1}^{n+1}\left(n+1\right)^2=\frac{\left(n+1\right)\left(\left(n+1\right)+1\right)\left(2\left(n+1\right)+1\right)}{6}\\\sum _{\left(n+1\right)=1}^{n+1}\left(n+1\right)^2=\left(n+1\right)^2+\sum _{n=1}^nn^2\\\mathrm{By\:induction\:hypothesis}\:\sum _{n=1}^nn^2=\frac{n\left(n+1\right)\left(2n+1\right)}{6}\\

To check whether it is true for all n.

(n+1)2+n(n+1)(2n+1)6=(n+1)(n+1+1)(2(n+1)+1)6Multiplybothsidesby6(n+1)26+n(n+1)(2n+1)66=(n+1)(n+1+1)(2(n+1)+1)666(n+1)2+n(n+1)(2n+1)=(n+1)(n+2)(2(n+1)+1)2(n+1)+1=2n+3(n+1)(n+2)=n2+3n+2(n2+3n+2)(2n+3)=2n3+9n2+13n+62n3+9n2+13n+6=2n3+9n2+13n+6Subtract6frombothsides2n3+9n2+13n+66=2n3+9n2+13n+662n3+9n2+13n=2n3+9n2+13nSubtract2n3+9n2+13nfrombothsides2n3+9n2+13n(2n3+9n2+13n)=2n3+9n2+13n(2n3+9n2+13n)0=0LHS=RHS\left(n+1\right)^2+\frac{n\left(n+1\right)\left(2n+1\right)}{6}=\frac{\left(n+1\right)\left(n+1+1\right)\left(2\left(n+1\right)+1\right)}{6}\\\mathrm{Multiply\:both\:sides\:by\:}6\\\left(n+1\right)^2\cdot \:6+\frac{n\left(n+1\right)\left(2n+1\right)}{6}\cdot \:6=\frac{\left(n+1\right)\left(n+1+1\right)\left(2\left(n+1\right)+1\right)}{6}\cdot \:6\\6\left(n+1\right)^2+n\left(n+1\right)\left(2n+1\right)=\left(n+1\right)\left(n+2\right)\left(2\left(n+1\right)+1\right)\\2\left(n+1\right)+1=2n+3\\\left(n+1\right)\left(n+2\right)=n^2+3n+2\\\left(n^2+3n+2\right)\left(2n+3\right)=2n^3+9n^2+13n+6\\2n^3+9n^2+13n+6=2n^3+9n^2+13n+6\\\mathrm{Subtract\:}6\mathrm{\:from\:both\:sides}\\2n^3+9n^2+13n+6-6=2n^3+9n^2+13n+6-6\\2n^3+9n^2+13n=2n^3+9n^2+13n\\\mathrm{Subtract\:}2n^3+9n^2+13n\mathrm{\:from\:both\:sides}\\2n^3+9n^2+13n-\left(2n^3+9n^2+13n\right)=2n^3+9n^2+13n-\left(2n^3+9n^2+13n\right)\\0=0\\LHS=RHS\\

Hence it is true for all n.

Example 4: Find the sum of n terms of 1+1+22+1+2+33..1+\frac{1+2}{2}+\frac{1+2+3}{3}……..

Solution:

Tn=1+2+3+..nnSn=Tn=1+2+3+..nn=(n(n+1))/2n=(n+1)/2=1/2(n+1)=12[n(n+1)2+n]=n(n+1)+2n4=n(n+3)4Tn= \frac{1+2+3+…..n}{n}\\ Sn = \sum Tn = \sum \frac{1+2+3+…..n}{n}\\ = \sum (n(n+1))/2n\\ =\sum (n+1)/2\\ = 1/2(\sum n + \sum 1)\\ = \frac{1}{2}[\frac{n(n+1)}{2}+n]\\ = \frac{n(n+1)+2n}{4}\\ = \frac{n(n+3)}{4}\\

Example 5: If x ∈ {1, 2 , 3 . . . . 9} and fn (x) = x x x . . . x (n digits), then what is f 2n(3) + fn (2)?

Solution:

fn(3) = 3 3 3 . . . 3 (n digits) and

f 2n(3) = 9 9 9 . . . 9 (n digits),

fn (2) = 2 2 2 . . . 2 (n digits)

∴ f 2n(3) + fn (2) = 1 2 . . . 2 2 2 1 ((n+1)digits)

fn (1) = 1 1 1 . . . 1 (n digits)

∴ f 2n(3) + fn (2) = 1 2 2 . . . 2 1 ((n+1)digits)

Example 6: If p(n) = n2 + n,∀ n ∈ N, then p(n) is _____________ integer. Justify.

Solution:

P(n) = n2 + n:

P(1) = 1 + 1 = 2;

P(2) = 22 + 2 = 6;

P(3) = 32 + 3 = 12

We observe that ∀n∈N,P(n) is always an even positive integer.

Example 7: The value of (2n)!22n(n!)\frac{(2n)!}{2^{2n}*(n!)} can be generally written in the form of _____________.

Solution:

By setting n = 1, we get (2n)!22n(n!)2\frac{(2n)!}{2^{2n}*(n!)^2} as (2)2212\frac{(2)}{2^{2}*1^2} = 24\frac{2}{4} = 12\frac{1}{2}

Upon setting n = 2 , (2n)!22n(n!)2\frac{(2n)!}{2^{2n}*(n!)^2} becomes 38\frac{3}{8}.

It can commonly be written in the form of 1(3n+1)12\frac{1}{(3n+1)^\frac{1}{2}}.

Example 8: The number (492 − 4) (493 − 49) is divisible by__ !.

Solution:

(492 − 4) (493 − 49) = (492 − 22) × 49 (492 − 1) = 51 * 47 * 49 * 50 * 48 = 51 * 50 * 49 * 48 * 47 is the product of five consecutive integers. Hence, it is divisible by 5!.

Example 9: What is the least positive remainder when 2301 is divided by 5?

Solution:

24 ≡ 1 (mod 5);

⇒(24)75 ≡ (1)75 (mod 5) i.e.

2300 ≡ 1 (mod 5)

⇒2300 × 2 ≡ (1.2) (mod 5)

⇒2301 ≡ 2 (mod 5),

∴ Least positive remainder is 2.

Up next Binomial Theorem

BOOK

Free Class