# Counting Principle - Concept with Problem | Combinatorics

Learn the concept of the Counting Principle and make algorithms to count complex things in a simpler way with the help of a beautiful problem of Combinatorics.

## Concept - Counting Principle.

Often we come across such problems that involves very complex counting which are nearly impossible to do in a trivial way. To encounter this kind of complexity of counting we use some $\textbf{tricks and tools}$; one of them is to find a algorithm or a pattern.

We try to obtain result for a similar but a simpler problem and then by the algorithm achieve the final goal.

## One Handy Tool - Multiplication Principle and Its Application In Set Theory

Suppose we have two sets $X=\{x_1,x_2,x_3\}$ and $Y=\{y_1,y_2\}$ ,then number of order pairs $(x_i,y_j);\text{ such that } i=1,2,3 ; j=1,2$ is equal to $3\times2=6$

That is , If a set $S_1$ has $n$ elements and the set $S_2$ has $m$ element then the set $S_1\times S_2=\{(a,b) | a \in S_1 , b \in S_2\}$ has $nm$ elements.

## Face the problem Now :

Let $S=\{1,2,3,\ldots ,10\}$ Find the number of subsets $A$ of $S$ such that $x\in A,$ and $2x \in S \Rightarrow 2x \in A$

### Key Concepts

Combinatorics

Counting

Set Theory

Answer: $180$

## Try with Hints

Understand The Problem :

What is the set $A$? Let us see some feasible options for $A$

$\{1,2,4,8\}, \{2,4,8\},\{1,3,2,4,8,6\} \ldots \text{etc.}$Is there any pattern ?

Ok wait !!!! There is one thing that if we take $1$ in $A$ then $2,4,8$ must belongs to $A$, similarly, if we take $3 \in A$ then $6\in A$ .

Good.... we are surely getting something interesting. Do you want to give it a thought ?

Let's Take a Simpler Example :

Let us see what happens if $S$ was given as $\{1,2,3\}$ , then all possible options of $A$ would be $\{1,2\}, \{2\}, \{3\}, \{2,3\}, \phi$. i.e, $6$ such possible options.

We can notice a very interesting thing here that the elements $1,2$ are making a group because twice of $1$ is $2$ let call them elements of $1^{st}$ kind and $3$ is not related to the elements by this kind of relation, let's call it element of 2^{nd} kind.

Then we can make two collection of sets $X=\{\{1,2\},\{2\},\phi \}$ and $Y=\{\{3\},\phi\}$ [That is $X$ contains all the subsets made by the elements of $1^{st}$ kind following the rule and $\phi$, similarly $Y$ contains the sets made by the elements of $2^{nd}$ kind following the rule and $\phi$ ].

Now , Let $P$ be the set $\{X'\cup Y' | \text{where} X' \in X \text{ and } Y' \in Y \}$ . Then member of $P$ are the possible options for $A$.

Therefore, $|P|=$ number of possible subset $A$ [where $|| \to$ number of elements in a set]. By the Multiplication Principle

$|P|=|X|\times |Y|=3\times 2=6$.

Finally, we have got a pattern. But !!! it will be better to check it for one more simpler example then we can definitely apply it to solve the original problem. Can you verify it for $S=\{1,2,3,4\}$

See!! we are getting a really good result.

For $S=\{1,2,3,4\}$

The element(s) of $1^{st}$ kind is/are : $1,2,4$.

The element(s) of $2^{nd}$ kind is/are : $3$ .

Then $X=\{\{1,2,4\},\{2,4\},\{4\},\phi\};\quad Y= \{\{3\},\phi\}$ .

Then $|P|=|X|\times |Y|=4\times 2=8$.

Now, if you count the possible subsets $A$ , you will get the same result. [They are $\{1,2,4\},\{2,4\}, \{4\}, \{3\}, \{1,2,3,4\}, \{2,3,4\}, \{3,4\}, \phi$]. So it works for $S=\{1,2,3,4\}$ .

Now you can easily apply the algorithm to the original problem.

Applying the algorithm for the original problem :

$S={1,2,3,\ldots,10}$..

Elements of $1^{st}$ kind : $1,2,4,8$.

Elements of $2^{nd}$ kind : $3,6$.

Elements of $3^{rd}$ kind : $5,10$.

Elements of $4^{th}$ kind : $7$

Elements of $5^{th}$ kind : $9$

Here $X=\{\{1,2,4,8\},\{2,4,8\},\{4,8\},\{8\},\phi\}$

$Y=\{\{3,6\},\{6\},\phi\}$

$Z=\{\{5,10\},\{10\},\phi\}$

$W=\{\{7\},\phi\}$

$U=\{\{9\},\phi\}$

$|P|=|X|\times|Y|\times|Z|\times|W|\times |U|$

$=5\times 3\times 3\times 2\times 2=180$ [ANS]

## Brain_Teaser : Generalize the concept

What if the set $S=\{1,2,\ldots,n\}$ i.e., Find the number of subsets $A$ of $S=\{1,2,\ldots,n\}$ such that $x\in A,$ and $2x \in S \Rightarrow 2x \in A$

# Rolle's Theorem | IIT JAM 2017 | Problem 10

Content
[hide]

Try this problem from IIT JAM 2017 exam (Problem 10).This problem needs the concept of Rolle's Theorem.

## Rolle's Theorem | IIT JAM 2017 | Problem 10

$$f(x)=\left\{\begin{array}{ll}1+x & \text { if } x<0 \\ (1-x)(p x+q) & \text { if } x \geq 0\end{array}\right.$$

satisfies the assumptions of Rolle's theorem in the interval $[-1,1],$ then the ordered pair $(p, q)$ is

• $(2,-1)$
• $(-2,-1)$
• $(-2,1)$
• $(2,1)$

### Key Concepts

Real Analysis

Continuity / Differentiability

Mean-value theorem of differential calculus

Answer: $(2,1)$

IIT JAM 2017 , Problem 10

Real Analysis : Robert G. Bartle

## Try with Hints

Rolle's Theorem :

Let a function $f:[a, b] \rightarrow R$ be such that

1. $f$ is continuous on $[a, b]$
2. $f$ is differentiable at every point of $(a, b)$
3. $f(a)=f(b)$

Then there exists at least one point $c \in(a, b)$ such that $f^{\prime}(c)=0$

We can easily see that $3^{rd}$ assumption of Rolle's theorem is satisfied for $f(x)$ irrespective of the values of $p,q$.

Since $f(-1)=0=f(1)\quad \forall p,q$

Since $f(x)$ satisfies $1^{st}$ assumption, then

\begin{aligned}& \quad \lim _{x \rightarrow 0^{-}} f(x)=\lim _{x \rightarrow 0^{+}} f(x)=f(0)\\&\text { ie, } \lim _{x \rightarrow 0^{-}}(1+x)=\lim _{x \rightarrow 0^{+}}(1-x)(px+q)=q\\&\Rightarrow 1=q\end{aligned}

$L f^{\prime}(0)=R f^{\prime}(0) \cdots \cdots(*)$

\begin{aligned} \text{Now, } L f^{\prime}(0) &=\lim _{h \rightarrow 0^{-}} \frac{f(0+h)-f(0)}{h} \\&=\lim _{h \rightarrow 0^{-}} \frac{(1+h)-q}{h} \\ &=\lim _{h \rightarrow 0^{-}} \frac{1+h-1}{h}[\text{because } q=1] \\&=\lim_{h \to 0^{-}} \frac hh\\&=1\end{aligned}

\begin{aligned}\text{and, } R f^{\prime}(0)&=\displaystyle\lim _{h \rightarrow 0^{+}} \frac{f(0+h)-f(0)}{h}\\&=\lim _{h \rightarrow 0^{+}} \frac{(1-h)\left(ph+q\right)-q}{h}\\&=\lim _{h \rightarrow 0^{+}} \frac{(1-h)(ph +1)-1}{h}\quad[\text{because } q=1]\\&=\lim _{h \rightarrow 0^{+}}\frac{ph+1- ph^{2}-h-1}{h}\\&=\lim _{h \rightarrow 0^{+}} \frac{h(p-ph-1)}{h}\\&=\lim_{h \ to 0^{+}} (p-ph-1)\\&=p-1\end{aligned}

Then by $(*) \text{we have}, \quad P-1=1 \Rightarrow P=2$

Then order pair $(p,q)\equiv (2,1)$ [ANS]

# Partial Differentiation | IIT JAM 2017 | Problem 5

Content
[hide]

Try this problem from IIT JAM 2017 exam (Problem 5) based on Partial Differentiation. It deals with calculating the partial derivative of a multi-variable function.

## Partial Differentiation | IIT JAM 2017 | Problem 5

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be a twice differentiable function. If $g(u, v)=f\left(u^{2}-v^{2}\right),$ then
$\frac{\partial^{2} g}{\partial u^{2}}+\frac{\partial^{2} g}{\partial v^{2}}=$

• $4\left(u^{2}-v^{2}\right) f^{\prime \prime}\left(u^{2}-v^{2}\right)$
• $4\left(u^{2}+v^{2}\right) f^{\prime \prime}\left(u^{2}-v^{2}\right)$
• $2 f^{\prime}\left(u^{2}-v^{2}\right)+4\left(u^{2}-v^{2}\right) f^{\prime \prime}\left(u^{2}-v^{2}\right)$
• $2(u-v)^{2} f^{\prime \prime}\left(u^{2}-v^{2}\right)$

### Key Concepts

Real Analysis

Function of Multi-variable

Partial Differentiation

Answer: $4\left(u^{2}+v^{2}\right) f^{\prime \prime}\left(u^{2}-v^{2}\right)$

IIT JAM 2017, Problem 5

Real Analysis : Robert G. Bartle

## Try with Hints

Here $g$ is a function of $u$ and $v$, to calculate $\frac{\partial g}{\partial u}$ we will differentiate the function $g$ with respect to $u$ keeping $v$ as constant.

and to calculate $\frac{\partial g}{\partial v}$ we will differentiate the function $g$ with respect to $v$ keeping $u$ as constant.

and $\frac{\partial^2 g}{\partial u^2}= \frac{\partial }{\partial u} [ \frac{\partial g}{\partial u} ]$

Hmm... I think you can easily do it from here ........

\begin{aligned}\frac{\partial^{2} g}{\partial u^{2}}=\frac{\partial}{\partial u}\left(\frac{\partial u}{\partial u}\right) &=\frac{\partial}{\partial u}\left[f^{\prime}\left(v^{2}-v^{2}\right) \cdot 2 u\right] \\&=2 u \cdot f^{\prime \prime}\left(v^{2}-v^{2}\right) \cdot 2 u+f^{\prime}\left(v^{2}-v^{2}\right) \cdot 2 \\&=4 u^{2} f^{\prime \prime}\left(v^{2}-v^{2}\right)+2 f^{\prime}\left(v^{2}-v^{2}\right)\ldots\ldots(i)\end{aligned}

Similarly,

\begin{aligned}\frac{\partial^{2} g}{\partial v^{2}}=\frac{\partial}{\partial v}\left(\frac{\partial g}{\partial v}\right) &=\frac{\partial}{\partial v}\left[f^{\prime}\left(v^{2}-v^{2}\right) \cdot (-2 v)\right] \\&=(-2 v) \cdot f^{\prime \prime}\left(v^{2}-v^{2}\right) \cdot (-2 v)+f^{\prime}\left(v^{2}-v^{2}\right) \cdot (-2) \\&=(4 v^{2}) f^{\prime \prime}\left(v^{2}-v^{2}\right)-2 f^{\prime}\left(v^{2}-v^{2}\right) \ldots\ldots(ii) \end{aligned}

Adding $(i)$ and (ii) we get,

$\frac{\partial^{2} g}{\partial u^{2}}+\frac{\partial^{2} g}{\partial x^{2}}$

$=4\left(u^{2}+v^{2}\right) f^{\prime \prime}\left(u^{2}-v^{2}\right)+2 f^{\prime}\left(u^{2}-v^{2}\right)-2 f^{\prime}\left(u^{2}-v^{2}\right)$

$=4\left(u^{2}+v^{2}\right) f^{\prime \prime}\left(u^{2}-v^{2}\right) \textbf{[Ans]}$

# Radius of Convergence of a Power series | IIT JAM 2016

Content
[hide]

Try this problem from IIT JAM 2017 exam (Problem 48) and know how to determine radius of convergence of a power series.

## Radius of Convergence of a Power Series | IIT JAM 2016 | Problem 48

Find the radius of convergence of the power series
$$\sum_{n=1}^{\infty} \frac{(-4)^{n}}{n(n+1)}(x+2)^{2 n}$$

### Key Concepts

Real Analysis

Series of Functions

Power Series

Answer: $\frac12$

IIT JAM 2016 , Problem 48

Real Analysis : Robert G. Bartle

## Try with Hints

Given, the power series is $\sum_{n=1}^{\infty} \frac{(-4)^{n}}{n(n+1)}(x+2)^{2 n}$.

Let us put $2n=m$ to get the standard form of a power series.

We get,

$\sum_{m=2}^{\infty} \frac{(-4)^{\frac m2}}{\frac m2(\frac m2+1)}(x+2)^{ m}$.

Now let us make the transformation $z=x+2$ to get a power series about 0 :

We have,

$\sum_{m=2}^{\infty} \frac{(-4)^{\frac m2}}{\frac m2(\frac m2+1)}(z)^{ m}$

Compairing with $\sum_{m=2}^{\infty} a_m (z)^m$

we get,

$a_m= \frac{(-4)^{\frac m2}}{\frac m2(\frac m2+1)}$

Now we have to test the convergence of the series.

Can you apply Ratio Test to check the convergence of the series.

Ratio Test : Let $\sum_{n=0}^{\infty} a_{n} x^{n}$ be a power series and let $\lim \left|\frac{a_{n+1}}{a_{n}}\right|=\mu .$ Then

1. if $\mu=0$ the series is everywhere convergent;
2. if $0<\mu<\infty$ the series is absolutely convergent for all $x$ satisfyir $|x|<\frac{1}{\mu}$ and the series is divergent for all $x$ satisfying $|x|>\frac{1}{\mu}$
3. if $\mu=\infty,$ the series is nowhere converegnt.

\begin{aligned}\left|\frac{a_{m+1}}{a_m}\right| &=\left| \frac{4^{\frac m2}\cdot 2\cdot4}{(m+1)(m+3)} \times \frac{m(m+2)}{4^{\frac m2} \cdot 4}\right| \\&=\left| \quad \frac{2\left(1+\frac{2}{m}\right)}{\left(1+\frac{1}{m}\right)(1+\frac 3m)}\right|\end{aligned}

Now

$\lim \left|\frac{a_{m+1}}{a_{m}}\right|=2 \in (0,\infty)$

Then, The given power series is absolutely convergent i.e., convergent $\forall x$ such that $|x+2|<\frac 12$

Then the answer is $\frac 12$

# Eigen Value of a matrix | IIT JAM 2017 | Problem 58

Content
[hide]

Try this problem from IIT JAM 2017 exam (Problem 58) and know how to evaluate Eigen value of a Matrix.

## Eigen value of a Matrix | IIT JAM 2017 | Problem 58

Let $\alpha, \beta, \gamma, \delta$ be the eigenvalues of the matrix
$$\begin{bmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{bmatrix}$$
Then find the value of $\alpha^{2}+\beta^{2}+\gamma^{2}+\delta^{2}$

### Key Concepts

Linear Algebra

Matrix

Eigen Values

Answer: $6$

IIT JAM 2017 , Problem 58

## Try with Hints

Characteristic Equation of a matrix $A$ of order $n$ is defined by $|A-xI|=0$, where $x$ is scalar and $I$ is the identity matrix of order $n$.

The roots of the characteristic equation are called the Eigen Values of that matrix.

Now it is easy. Give it a try.

Let

$$A=\begin{bmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{bmatrix}$$

Then its characteristic equation is $|A-xI|=0$ for some scalar $x$ and $I$ the identity matrix of order $4$

i.e., $\begin{vmatrix} -x & 0 & 0 & 0 \\ 1 & -x & 0 & -2 \\ 0 & 1 & -x & 1 \\ 0 & 0 & 1 & 2-x \end{vmatrix} =0$

$\Rightarrow -x\begin{vmatrix} -x & 0 & -2 \\ 1 & -x & 1 \\ 0 & 1 & 2-x \end{vmatrix} =0$

$\Rightarrow -x[-x\{(-x)(2-x)\}-1]-2(1-0)]=0$

$\Rightarrow x^{4}-2 x^{3}-x^{2}+2 x=0$

$\Rightarrow x(x^{3}-2 x^{2}-x+2)=0$

$\Rightarrow x(x-1)(x-2)(x+1)=0$

Then the eigen values are : $0,1,-1,2$

Then, $\alpha^{2}+\beta^{2}+\gamma^{2}+\delta^{2} =0^2+1^2+(-1)^2+2^2=6$ [ANS]

# Limit of a function | IIT JAM 2017 | Problem 8

Content
[hide]

Try this problem from IIT JAM 2017 exam. It deals with evaluating Limit of a function.

## Limit of a Function | IIT JAM 2017 | Problem 8

Let $$f(x)=\frac{x+|x|(1+x)}{x} \sin \left(\frac{1}{x}\right), \quad x \neq 0$$
Write $L=\displaystyle\lim_{x \to 0^{-}} f(x)$ and $R=\displaystyle\lim_{x \to 0^{+}} f(x) .$

Then which one of the following is true?

• $L$ exists but $R$ does not exist
• $L$ does not exist but $R$ exists
• Both $L$ and $R$ exist
• Neither $L$ nor $R$ exists

### Key Concepts

Real Analysis

Function

Limit

Answer: $L$ exists but $R$ does not exists

IIT JAM 2017 , Problem 8

## Try with Hints

Given that, $f(x)=\frac{x+|x|(1+x)}{x} \sin \left(\frac{1}{x}\right), \quad x \neq 0$

therefore,

$f(x)=1+\frac{|x|}{x}(1+x) \sin \left(\frac{1}{x}\right), \quad x \neq 0$

$f(x)=\bigg\{\begin{array}{cc} (2+x) \sin \left(\frac{1}{x}\right), & , x>0 \\ -x \sin \left(\frac{1}{x}\right), & x<0 \\ \end{array}$

Let, $L=\displaystyle\lim_{x \to 0^{-}} f(x)$

and , $R= \displaystyle \lim_{x \rightarrow 0^{+}} f(x) .$

Now,

$L= \displaystyle\lim_{x \to 0^{-}} f(x)$

$\quad = \displaystyle\lim_{x \to 0^{-}} -x \sin \left(\frac{1}{x}\right)$

$\quad = -\displaystyle\lim_{x \to 0^{-}} x \sin \left(\frac{1}{x}\right)$

Theorem : If $D \subset \mathbb R$ and $f,g : D \to \mathbb R$ . Let $c \in D$. If f is bounded on $N'(c)\cup D$ and $\displaystyle\lim_{x \to c} g(x)=0$, then $\displaystyle\lim_{x \to c}(f.g)(x)=0$.

Now , $\sin \left(\frac{1}{x}\right)$ is bounded in $\mathbb R - \{0\}$ and $\displaystyle\lim_{x \to 0^{-}} x=0$ , then $\displaystyle\lim_{x \to 0^{-}} f(x)$ exists and equal to $0$.

But,

$R=\displaystyle\lim_{x\to 0^{+}}f(x)$

$\quad = \displaystyle\lim_{x\to 0^{+}} (2+x) \sin \left(\frac{1}{x}\right),$

$\quad= \displaystyle\lim_{x\to 0^{+}} 2\sin \left(\frac{1}{x}\right) + x \sin \left(\frac{1}{x}\right)$

$\lim_{x \to 0^{+}} \sin \left(\frac{1}{x}\right)$ does not exists [Why?]

Then $L$ exists but $R$ does not.

# Gradient, Divergence and Curl | IIT JAM 2014 | Problem 5

Content
[hide]

Try this problem from IIT JAM 2014 exam. It deals with calculating Gradient of a scalar point function, Divergence and curl of a vector point function.

## $\nabla, \nabla ., \nabla \times$ Operators | IIT JAM 2014 | Problem 5

If $f(x,y,z)=x^2y+y^2z+z^2x,\quad \forall (x,y,z) \in \mathbb R$ and $\nabla=(\frac{\partial}{\partial x}\hat{i}+ \frac{\partial}{\partial y}\hat{j}+ \frac{\partial}{\partial z}\hat{k} )$ then the value of $\nabla.(\nabla \times \nabla f)+\nabla.(\nabla f)$ at $(1,1,1)$

• $4$
• $5$
• $6$
• $7$

### Key Concepts

Vector Calculus

Scalar Point Function

Answer: $6$

IIT JAM 2014 , Problem 5

## Try with Hints

Scalar Point Function : is a function which assigns a point$(x,y,z) \in \mathbb R^3$ to a scalar. Here $f$ is a scalar point function.

$\nabla=(\frac{\partial}{\partial x}\hat{i}+ \frac{\partial}{\partial y}\hat{j}+ \frac{\partial}{\partial z}\hat{k} )$

Gradient of a function :($\nabla f) = (\frac{\partial f}{\partial x}\hat{i}+ \frac{\partial f}{\partial y}\hat{j}+ \frac{\partial f}{\partial z}\hat{k} )$

Divergence of a function ($\nabla.\vec F$) =$(\frac{\partial}{\partial x}\hat{i}+ \frac{\partial}{\partial y}\hat{j}+ \frac{\partial}{\partial z}\hat{k} ).\vec F$

Curl of a function ($\nabla\times \vec F$) =$(\frac{\partial}{\partial x}\hat{i}+ \frac{\partial}{\partial y}\hat{j}+ \frac{\partial}{\partial z}\hat{k} )\times \vec F$

Now, $\nabla f = (2xy+z^2) \hat{i}+(2yz+x^2)\hat{j}+(2zx+y^2)\hat{k}$

Therefore $\nabla . (\nabla f)=\frac{\partial}{\partial x}(2xy+z^2)+ \frac{\partial}{\partial y}(2yz+z^2) + \frac{\partial}{\partial z}(2zx+y^2)$

$\quad= 2x+2y+2z$

Again,

$\nabla \times \nabla f = \begin{vmatrix} \hat i & \hat j & \hat k \\ \frac{\partial}{\partial x} & \frac{\partial}{\partial y} & \frac{\partial}{\partial z} \\ 2xy+z^2 & 2yz+x^2 & 2zx+y^2\end{vmatrix}= \vec 0$

Therefore $\nabla. (\nabla \times \nabla f)= 0$

then, $\nabla.(\nabla \times \nabla f)+\nabla.(\nabla f) = 2(x+y+z) \bigg|_{(1,1,1)}=6$

# Differential Equation| IIT JAM 2014 | Problem 4

Content
[hide]

Try this problem from IIT JAM 2014 exam. It requires knowledge of the exact differential equation and partial derivative.

## Differential Equation | IIT JAM 2014 | Problem 4

For $a,b,c \in \mathbb R$, If the differential equation $(ax^2+bxy+y^2)\mathrm d x+(2x^2+cxy+y^2)\mathrm d y=0$ is exact then

• $b=2,c=2a$
• $b=4,c=2$
• $b=2,c=4$
• $b=2,a=2c$

### Key Concepts

Differential Equation

Exact D/E

Partial Differentiation

Answer: $b=4, c=2$

IIT JAM 2014 , Problem 4

Ordinary Differential Equations by Tenebaum and Pollard

## Try with Hints

Any first order and linear differential equation can be expressed as

$M(x,y)\mathrm d x+N(x,y)\mathrm d y=0 \cdots\cdots\cdots (i)$ where $M$ and $N$ are functions of $x$ and $y$.

$(i)$ is called exact if and only if $\frac{\partial M}{\partial y}=\frac{\partial N}{\partial x}$

Comparing the given equation with $(i)$ we get,

$M(x,y)=(ax^2+bxy+y^2)$

$N(x,y)=(2x^2+cxy+y^2)$

Now can you calculate $\frac{\partial M}{\partial y}\text{ and }\frac{\partial N}{\partial x}$ ?

$\frac{\partial M(x,y)}{\partial y}=2y+bx$ [differentiating $M(x,y)$ with respect to $y$ taking $x$ as constant.]

$\frac{\partial N(x,y)}{\partial x}=4x+cy$ [differentiating $N(x,y)$ with respect to $x$ taking $y$ as constant.]

Since the equation is exact ,then$\frac{\partial M}{\partial y}=\frac{\partial N}{\partial x}$

i.e., $2y+bx=4x+cy$

Comparing the coefficients we get $b=4,c=2$ [ANS]

# Definite Integral as Limit of a sum | ISI QMS | QMA 2019

Content
[hide]

Try this problem from ISI QMS 2019 exam. It requires knowledge Real Analysis and integral calculus and is based on Definite Integral as Limit of a sum.

## Definite integral as Limit of a Sum - ISI QMS (QMB Problem 1a)

Find the value of : $\displaystyle \lim_{n \to \infty}\big[\frac1n+\frac{1}{n+1}+\ldots + \frac{1}{3n}\big]$

### Key Concepts

Real Analysis

Definite Integral

Riemann Sum

Answer: $\ln 3$

ISI QMS 2019 (QMB Problem 1a)

Secrets in Inequalities

## Try with Hints

Putting it into standard form :

$\displaystyle\lim_{n \to \infty} \big[\frac{1}{n}+\frac{1}{n+1}+\ldots+\frac{1}{3n}\big]$

$= \displaystyle \lim_{n\to \infty}\big[\frac{1}{n+0}+\frac{1}{n+1}+\ldots+\frac{1}{n+2n}\big]$

$= \displaystyle \lim_{n \to \infty} \displaystyle\sum_{r=0}^{2n} \frac{1}{n+r}$

$= \displaystyle \lim_{n \to \infty} \frac1n\displaystyle\sum_{r=0}^{2n} \frac{1}{1+\frac rn}$

$= \displaystyle \lim_{n \to \infty} \frac1n\displaystyle\sum_{r=0}^{2n} f(\frac rn)$ where $f(x)=\frac{1}{1+x}$

An useful result : Let $f:[a,b]\to \mathbb R$ be integrable on $[a,b]$ and $\{P_n\}$ be a sequence of partitions of $[a,b]$ such that the sequence $\{\parallel P_n\parallel\}$ converges to $0$. Then if $\epsilon >0$ be given, there exists a natural number $k$ such that $|S(P_n, f)-\int_a^b f|<\epsilon \quad \forall n\geq k$ where $S(P,f)$ is a Riemann sum of $f$ corresponding to $P$ and any choice of intermediate points.

i.e., If $f$ be integrable on $[a,b]$ and $\{P_n\}$ be a sequence of partitions of $[a,b]$ such that $\lim\limits_{n \to \infty} \parallel P_n \parallel=0$, then $\lim\limits_{n\to \infty} S(P_n,f)=\int_a^b f$

Let $P_n=(0,\frac1n,\frac2n,\ldots,\frac{2n}{n})$ be a sequence of partition on $[0,2]$ dividing it into $2n$ sub-intervals of equal length $\frac1n$.

Also $\lim \parallel P_n\parallel=\lim \frac1n=0$.

Let us choose $\xi_r=\frac rn,\quad r=1,2,3,\ldots,2n$

Then the Riemann sum for $f$ on the interval $[0,2]$ corresponding to the partition $P_n$ and chosen intermediate points $\xi_r$

$S(P_n,f)=\frac1n\displaystyle\sum_{r=1}^{2n} f(\frac rn)$

As $f$ is continuous on $[0,2]$, $f$ is integrable on $[0,2]$.

Now can you use the above result to reach to the solution ?

Using the result

$\lim\limits_{n\to\infty} \frac1n\displaystyle\sum_{r=1}^{2n} f(\frac rn) = \displaystyle\int_0^2 f(x) \mathrm d x$

$= \displaystyle\int_0^2 \frac{ \mathrm d x }{1+x}$

$=\ln(1+x)\bigg|_0^2= \ln 3$ [Ans]

# Minimal Polynomial of a Matrix | TIFR GS-2018 (Part B)

Content
[hide]

Try this beautiful problem from TIFR GS 2018 (Part B) based on Minimal Polynomial of a Matrix. This problem requires knowledge of linear algebra.

## Minimal Polynomial of a matrix - TIFR GS- Part B (Problem 10)

The minimal polynomial of $\begin{pmatrix} 2 &1& 0&0 \\ 0 &2&0&0 \\ 0&0&2&0\\ 0&0&1&5\end{pmatrix}$ is

• $(x-2)(x-5)$
• $(x-2)^2(x-5)$
• $(x-2)^3(x-5)$
• None of these

### Key Concepts

Linear Algebra

Matrix / Vector Space

Characteristic Polynomial

Answer: $(x-2)^2(x-5)$

TIFR GS -2018 (Part- B) | Problem No 10

Graduate Texts in Mathematics : Springer-Verlag

## Try with Hints

Some Definitions and Results Needed :

1. Monic Polynomial : A polynomial is said to be monic if the coefficient of the highest degree term is 1.
2. Characteristic Polynomial of a matrix : Let $A$ be a square matrix of order $n$ then the polynomial $|A-\lambda I_n|$ is called its characteristic polynomial and $|A-\lambda I_n|=0$ is called the characteristic equation. [$I_n$ is the identity matrix of order $n$]
3. Cayley - Hamilton Theorem : If $p(\lambda)$ is the characteristic polynomial of an $n\times n$ matrix $A$ over a field $F$, then the matrix $A$ satisfies the equation $p(x)=0$, i.e., $p(A)=0$. In other words, every square matrix satisfies its own characteristic equation.
4. Minimal Polynomial : The monic polynomial of lowest degree satisfied by a square matrix $A$ is called its minimal polynomial
5. Let $p(\lambda)$ and $m(\lambda)$ be the characteristic and minimal polynomials of a square matrix $A$ of order $n$ respectively. Then either both $p(\lambda)$ and $m(\lambda)$ are of degree $n$ or $m(\lambda)$ is a factor of $p(\lambda)$ .
6. Minimal polynomial is unique.

So all the ingredients you need to cook the problem are given... Can you make it delicious ?

To find the Characteristic equation of the given matrix :

Let $A= \begin{pmatrix} 2 &1& 0&0 \\ 0 &2&0&0 \\ 0&0&2&0\\ 0&0&1&5\end{pmatrix}$

Then, $|A-\lambda I_4|= \begin{vmatrix} 2-\lambda &1& 0&0 \\ 0 &2-\lambda &0&0 \\ 0&0&2-\lambda &0\\ 0&0&1&5-\lambda \end{vmatrix}$

$\quad = (2-\lambda)^3(5-\lambda) = p(\lambda)$ [say]

then, the characteristic equation of $A$ is $p(x)=(x-2)^3(x-5)=0$

Then By Cayley Hamilton Theorem $(A-2I_4)^2(A-5I_4)=O_{4 \times 4}$ [$O_{4 \times 4}$ is the NULL MATRIX of order $4$]

As minimal polynomial is unique then if minimal polynomial is a polynomial of degree $4$ it is same as the characteristic polynomial by Property 5 in the first hint and if minimal polynomial is less than degree $4$ then it is a factor of characteristic polynomial.

all the factors of characteristic polynomial are :

$p_1(x)=(x-2)(x-5),\quad p_2(x)=(x-2)^2(x-5),\\ \text{ and } p(x)=(x-2)^3(x-5)$

Lets Find $p_1(A)$ i.e., $(A-2I_4)(A-5I_4)$ :

$(A-2I_4)(A-5I_4)=\begin{pmatrix} 0 &1& 0&0 \\ 0 &0&0&0 \\ 0&0&0&0\\ 0&0&1&3\end{pmatrix} \times \begin{pmatrix} -3 &1& 0&0 \\ 0 &-3&0&0 \\ 0&0&-3&0\\ 0&0&1&0\end{pmatrix}$

$\quad\quad= \begin{pmatrix} 0 &-3& 0&0 \\ 0 &0&0&0 \\ 0&0&0&0\\ 0&0&0&0\end{pmatrix} \ne O_{4 \times 4}$

Now, $p_2(A)$ i.e., $(A-2I_4)^2(A-5I_4)$ :

$(A-2I_4)^2(A-5I)=\begin{pmatrix} 2 &1& 0&0 \\ 0 &2&0&0 \\ 0&0&2&0\\ 0&0&1&5\end{pmatrix}^2 \times \begin{pmatrix} -3 &1& 0&0 \\ 0 &-3&0&0 \\ 0&0&-3&0\\ 0&0&1&0\end{pmatrix}$

$\quad\quad= \begin{pmatrix} 0 &0& 0&0 \\ 0 &0&0&0 \\ 0&0&0&0\\ 0&0&3&9\end{pmatrix} \times \begin{pmatrix} -3 &1& 0&0 \\ 0 &-3&0&0 \\ 0&0&-3&0\\ 0&0&1&0\end{pmatrix} = O_{4 \times 4}$

Therefore the lowest degree monic polynomial satisfied by $A$ is $(x-2)^2(x-5)$.

Hence the minimal polynomial is $(x-2)^2(x-5)$