Practice questions based on combinatorics for RMO Training and IITJEE Mathematics

Question 1:

Prove that if n is an even integer, then

$\frac{1}{(1!)(n-1)!} + \frac{1}{3! (n-3)!} + \frac{1}{5! (n-5)!} + \ldots + \frac{1}{(n-1)! 1!} = \frac{2^{n-1}}{n!}$

Question 2:

If ${n \choose 0}$ , ${n \choose 1}$ , ${n \choose 2}$ , …. ${n \choose n}$ are the coefficients in the expansion of $(1+x)^{n}$ , when n is a positive integer, prove that

(a) ${n \choose 0} - {n \choose 1} + {n \choose 2} - {n \choose 3} + \ldots + (-1)^{r}{n \choose r} = (-1)^{r}\frac{(n-1)!}{r! (n-r-1)!}$

(b) ${n \choose 0} - 2{n \choose 1} + 3{n \choose 2} - 4{n \choose 3} + \ldots + (-1)^{n}(n+1){n \choose n}=0$

(c) ${n \choose 0}^{2} - {n \choose 1}^{2} + {n \choose 2}^{2} - {n \choose 3}^{2} + \ldots + (-1)^{n}{n \choose n}^{2}=0$ , or $(-1)^{\frac{n}{2}}{n \choose {n/2}}$ , according as n is odd or even.

Question 3:

If $s_{n}$ denotes the sum of the first n natural numbers, prove that

(a) $(1-x)^{-3}=s_{1}+s_{2}x+s_{3}x^{2}+\ldots + s_{n}x^{n-1}+\ldots$

(b) $2(s_{1}s_{2m} + s_{2}s_{2n-1} + \ldots + s_{n}s_{n+1}) = \frac{2n+4}{5! (2n-1)!}$

Question 4:

If $q_{n}=\frac{1.3.5.7...(2n-1)}{2.4.6.8...2n}$ , prove that

(a) $q_{2n+1}+q_{1}q_{2n}+ q_{2}q_{2n-1} + \ldots + q_{n-1}q_{n+2} + q_{n}q_{n+1}= \frac{1}{2}$

(b) $2(q_{2n}-q_{1}q_{2m-1}+q_{2}q_{2m-2}+\ldots + (-1)^{m}q_{m-1}q_{m+1}) = q_{n} + (-1)^{n-1}{q_{n}}^{2}$ .

Question 5:

Find the sum of the products, two at a time, of the coefficients in the expansion of $(1+x)^{n}$ , where n is a positive integer.

Question 6:

If $(7+4\sqrt{3})^{n} = p + \beta$ , where n and p are positive integers, and $\beta$ , a proper fraction, show that $(1-\beta)(p+\beta)=1$ .

Question 7:

If ${n \choose 0}$ , ${n \choose 1}$ , ${n \choose 2}$ , …,, ${n \choose n}$ are the coefficients in the expansion of $(1+x)^{n}$ , where n is a positive integer, show that

${n \choose 1} - \frac{{n \choose 2}}{2} + \frac{{n \choose 3}}{3} - \ldots + \frac{(-1)^{n-1}{n \choose n}}{n} = 1 + \frac{1}{2} + \frac {1}{3} + \frac{1}{4} + \ldots + \frac{1}{n}$ .

That’s all for today, folks!

Nalin Pithwa.

Combinatorics for RMO : some basics and examples: homogeneous products of r dimensions

Posted by Nalin Pithwa

Question:

Find the number of homogeneous products of r dimensions that can be formed out of the n letters a, b, c ….and their powers.

Solution:

By division, or by the binomial theorem, we have:

$\frac{1}{1-ax} = 1 + ax + a^{2}x^{2} + a^{3}x^{3} + \ldots$

$\frac{1}{1-bx} = 1+ bx + b^{2}x^{2} + a^{3}x^{3} + \ldots$

$\frac{1}{1-cx} = 1 + cx + c^{2}x^{2} + c^{3}x^{3} + \ldots$

Hence, by multiplication,

$\frac{1}{1-ax} \times \frac{1}{1-bx} \times \frac{1}{1-cx} \times \ldots$

$= (1+ax + a^{2}x^{2}+a^{3}x^{3}+ \ldots)(1+bx + b^{2}x^{2} + b^{3}x^{3}+ \ldots)(1+cx + c^{2}x^{2} + c^{3}x^{3}+ \ldots)\ldots$

$= 1 + x(a + b + c + \ldots) +x^{2}(a^{2}+ab+ac+b^{2}+bc + c^{2} + \ldots) + \ldots$

$= 1 + S_{1}x + S_{2}x^{2} + S_{3}x^{3} + \ldots$ suppose;

where $S_{1}$ , $S_{2}$ , $S_{3}$ , $\ldots$ are the sums of the homogeneous products of one, two, three, … dimensions that can be formed of a, b, c, …and their powers.

To obtain the number of these products, put a, b, c, …each equal to 1; each term in $S_{1}$ , $S_{2}$ , $S_{3}$ , …now becomes 1, and the values of $S_{1}$ , $S_{2}$ , $S_{3}$ , …so obtained give the number of the homogeneous products of one, two, three, ….dimensions.

Also,

$\frac{1}{1-ax} \times \frac{1}{1-bx} \times \frac{1}{1-cx} \ldots$

becomes $\frac{1}{(1-x)^{n}}$ , or $(1-x)^{-n}$

Hence, $S_{r} =$ the coefficient of $x^{r}$ in the expansion of $(1-x)^{-n}$

$= \frac{n(n+1)(n+2)(n+3)\ldots (n+r-1)}{r!}= \frac{(n+r-1)!}{r!(n-1)!}$

Question:

Find the number of terms in the expansion of any multinomial when the index is a positive integer.

Answer:

In the expansion of $(a_{1}+ a_{2} + a_{3} + \ldots + a_{r})^{n}$

every term is of n dimensions; therefore, the number of terms is the same as the number of homogeneous products of n dimensions that can be formed out of the r quantities $a_{1}$ , $a_{2}$ , $a_{3}$ , … $a_{r}$ , and their powers; and therefore by the preceding question and solution, this is equal to

$\frac{(r+n-1)!}{n! (r-1)!}$

A theorem in combinatorics:

From the previous discussion in this blog article, we can deduce a theorem relating to the number of combinations of n things.

Consider n letters a, b, c, d, ….; then, if we were to write down all the homogeneous products of r dimensions, which can be formed of these letters and their powers, every such product would represent one of the combinations, r at a time, of the n letters, when any one of the letters might occur once, twice, thrice, …up to r times.

Therefore, the number of combinations of n things r at a time when repetitions are allowed is equal to the number of homogeneous products of r dimensions which can be formed out of n letters, and therefore equal to $\frac{(n+r-1)!}{r!(n-1)!}$ , or ${{n+r-1} \choose r}$ .

That is, the number of combinations of n things r at a time when repetitions are allowed is equal to the number of combinations of $n+r-1$ things r at a time when repetitions are NOT allowed.

We conclude this article with a few miscellaneous examples:

Example 1:

Find the coefficient of $x^{r}$ in the expansion of $\frac{(1-2x)^{2}}{(1+x)^{3}}$

Solution 1:

The expression $= (1-4x+4x^{2})(1+p_{1}x+p_{2}x^{2}+ \ldots + p_{r}x^{r}+ \ldots)$ , suppose.

The coefficients of $x^{r}$ will be obtained by multiplying $p_{r}$ , $p_{r-1}$ , $p_{r-2}$ by 1, -4, and 4 respectively, and adding the results; hence,

the required coefficient is $p_{r} - 4p_{r-1}+4p_{r-2}$

But, with a little work, we can show that $p_{r} = (-1)^{r}\frac{(r+1)(r+2)}{2}$ .

Hence, the required coefficient is

$= (-1)^{r}\frac{(r+1)(r+2)}{2} - 4(-1)^{r-1}\frac{r(r+1)}{2} + 4 (-1)^{r-2}\frac{r(r-1)}{2}$

$= \frac{(-1)^{r}}{2}\times ((r+1)(r+2) + 4r(r+1) + 4r(r-1))$

$= \frac{(-1)^{r}}{2}(9r^{2}+3r+2)$

Example 2:

Find the value of the series

$2 + \frac{5}{(2!).3} + \frac{5.7}{3^{2}.(3!)} + \frac{5.7.9}{3^{3}.(4!)} + \ldots$

Solution 2:

The expression is equal to

$2 + \frac{3.5}{2!}\times \frac{1}{3^{2}} + \frac{3.5.7}{3!}\times \frac{1}{3^{3}} + \frac{3.5.7.9}{4!}\times \frac{1}{3^{4}} + \ldots$

$= 2 + \frac{\frac{3}{2}.\frac{5}{2}}{2!} \times \frac{2^{2}}{3^{2}} + \frac{\frac{3}{2}.\frac{5}{2}.\frac{7}{2}}{3!} \times \frac{2^{3}}{3^{3}} + \frac{\frac{3}{2}.\frac{5}{2}.\frac{7}{2}.\frac{9}{2}}{4!} \times \frac{2^{4}}{3^{4}} + \ldots$

$= 1 + \frac{\frac{3}{2}}{1} \times \frac{2}{3} + \frac{\frac{3}{2}.\frac{5}{2}}{2!} \times (\frac{2}{3})^{2} + \frac{\frac{3}{2}.\frac{5}{2}.\frac{7}{2}}{3!} \times (\frac{2}{3})^{3} + \frac{\frac{3}{2}.\frac{5}{2}.\frac{7}{2}.\frac{9}{2}}{4!} \times (\frac{2}{3})^{4} + \ldots$

$= (1-\frac{2}{3})^{\frac{-3}{2}} = (\frac{1}{3})^{-\frac{3}{2}} = 3^{\frac{3}{2}} = 3 \sqrt{3}$ .

Example 3:

If n is any positive integer, show that the integral part of $(3+\sqrt{7})^{n}$ is an odd number.

Solution 3:

Suppose I to denote the integral and f the fractional part of $(3+\sqrt{7})^{n}$ .

Then, $I + f = 3^{n} + {n \choose 1}3^{n-1}\sqrt{7} + {n \choose 2}3^{n-2}.7 + {n \choose 3}3^{n-3}.(\sqrt{7})^{3}+ \ldots$ …call this relation 1.

Now, $3 - \sqrt{7}$ is positive and less than 1, therefore $(3-\sqrt{7})^{n}$ is a proper fraction; denote it by $f^{'}$ ;

Hence, $f^{'} = 3^{n} - {n \choose 1}.3^{n-1}.\sqrt{7} + {n \choose 2}.3^{n-2}.7 - {n \choose 3}.3^{n-3}.(\sqrt{7})^{3}+ \ldots$ …call this as relation 2.

Add together relations 1 and 2; the irrational terms disappear, and we have

$I + f + f^{'} = 2(3^{n} + {n \choose 2}.3^{n-2}.7+ \ldots ) = an even integer$

But, since f and $f^{'}$ are proper fractions their sum must be 1;

Hence, I is an odd integer.

Hope you had fun,

Nalin Pithwa.

Science Lives: Laslo Lovasz: Discrete Maths, Combinatorics and Computer Science

Posted by Nalin Pithwa

Thanks to Simon Foundation : a youtube video.

Inequalities and mathematical induction: RMO sample problems-solutions

Posted by Nalin Pithwa

Problem:

1. Prove the inequality —- $2^{n}(n!)^{2} \leq (2n)!$ for all natural numbers greater than or equal to 1.

Proof 1:

First consider the following: $2.6. 10.14 \ldots (4n-2)=\frac{(2n)!}{n!}$ . Let us prove this claim first and then use it to prove what is asked: Towards, that end, consider

$RHS = \frac{(2n)(2n-1)(2n-2)(2n-3)(2n-4)\ldots 4.2.1}{1.2.3.4\ldots (n-1)n}=LHS$ , cancelling off the common factors in numerator and denominator of RHS. (note this can also be proved by mathematical induction! 🙂 )

In the given inequality:

we need to prove $2^{n}(n!)^{2} \leq (2n)!$

consider $2.6.10.14. \ldots (4n-2)=\frac{(2n)!}{n!}$ where

LHS = $(2.1)(2.3) (2.5) (2.7) \ldots 2(n-1)$ , this is an AP with first term 2 and nth term $(4n-2)$ and common difference 4; there are n factors “2”; hence, we $2^{n}1.3.5.7 \ldots (n-1)=\frac{(2n)!}{n!}$ so we get

$2^{n} (n!) 1.3.5.7.\ldots (n-1) = (2n)!$ ; multiplying and dividing RHS of this by $2.4.6.8.\ldots n$ , we get the desired inequality. Remember the inequality is less than or equal to.

Problem 2:

Establish the Bernoulli inequality: If $(1+a) > 0$ , then $(1+a)^{n} \geq 1+na$ .

Solution 2:

Apply the binomial theorem, which in turn, is proved by mathematical induction ! 🙂

Problem 3:

For all natural numbers greater than or equal to 1, prove the following by mathematical induction:

$\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{n^{2}} \leq 2-\frac{1}{n}$

Proof 3:

Let the given proposition be P(n).

Step 1: Check if P(1) is true. Towards that end:

$LHS=\frac{1}{1^{2}}=1$ and $latex RHS=2-\frac{1}{1}=2-1=1$ and hence, P(1) is true.

Step 2: Let P(n) be true for some $n=k$ , $k \in N$ . That is, the following is true:

$\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{k^{2}} \leq 2 -\frac{1}{k}$

Add $\frac{1}{(k+1)^{2}}$ to both sides of above inequality, we get the following:

$\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{k^{2}} + \frac{1}{(k+1)^{2}} \leq 2-\frac{1}{k}+\frac{1}{(k+1)^{2}}$

Now, the RHS in above is $2-\frac{1}{k} +\frac{1}{(k+1)^{2}}=2-\frac{k^{2}+k+1}{k(k+1)^{2}}$ . We want this to be less than or equal to $2-\frac{1}{k+1}$ . Now, $k \in N$ , $k>1$ , so what we have to prove is the following:

$-\frac{k^{2}+k+1}{k(k+1)^{2}} \leq -\frac{1}{k+1}$ , that is, we want to prove that

$(k+1)(k^{2}+k+1) \geq k(k^{2}+2k+1)$ , that is, we want $k^{3}+k^{2}+k+k^{2}+k+1 \geq k^{3}+2k^{2}+k$ , that is, we want $k+1 \geq 0$ , which is obviously true. QED.

Cheers,

Nalin Pithwa.

RMO Training: more help from Nordic mathematical contest

Posted by Nalin Pithwa

Problem:

32 competitors participate in a tournament. No two of them are equal and in a one against one match the better always wins. (No tie please). Show that the gold, silver and bronze medal can be found in 39 matches.

Solution:

We begin by determining the gold medallist using classical elimination, where we organize 16 pairs and matches, then 8 matches of the winners, 4 matches of the winners in the second round, then 2-semifinal matches and finally one match making 31 matches altogether.

Now, the second best player must have at some point lost to the best player, and as there were 5 rounds in the elimination, there are 5 candidates for the silver medal. Let $C_{i}$ be the candidate who lost to the gold medalist in round i. Now, let $C_{1}$ and $C_{2}$ play, the winner play against $C_{3}$ , and so forth. After 4 matches, we know the silver medalist; assume this was $C_{k}$ .

Now, the third best player must have lost against the gold medalist or against $C_{k}$ or both. (If the player had lost to someone else, there would be at least three better players.) Now, $C_{k}$ won k-1 times in the elimination rounds, the 5-k players $C_{k+1}\ldots C_{5}$ and if k is greater than one, one player $C_{j}$ with $j<k$ . So there are either $(k-1)+(5-k)=4$ or $(k-1)+(5-k)+1=5$ candidates for the third place. At most 4 matches are again needed to determine the bronze winners.

Cheers to Norway mathematicians!

Nalin Pithwa.

Reference: Nordic mathematical contests, 1987-2009.

Amazon India link:

https://www.amazon.in/Nordic-Mathematical-Contest-1987-2009-Todev/dp/1450519830/ref=sr_1_1?s=books&ie=UTF8&qid=1518386661&sr=1-1&keywords=Nordic+mathematical+contest

RMO 2017 Warm-up: Two counting conundrums

Posted by Nalin Pithwa

Problem 1:

There are n points in a circle, all joined with line segments. Assume that no three (or more) segments intersect in the same point. How many regions inside the circle are formed in this way?

Problem 2:

Do there exist 10,000 10-digit numbers divisible by 7, all of which can be obtained from one another by a re-ordering of their digits?

Solutions will be put up in a couple of days.

Nalin Pithwa.

Math concept(s) : simple yet subtle

Posted by Nalin Pithwa

Most math concepts are intuitive, simple, yet subtle. A similar opinion is expressed by Prof. Michael Spivak in his magnum opus, Differential Geometry (preface). It also reminds me — a famous quote of the ever-quotable Albert Einstein: “everything should be as simple as possible, and not simpler.”

I have an illustrative example of this opinion(s) here:

Consider the principle of mathematical induction:

Most students use the first version of it quite mechanically. But, is it really so? You can think about the following simple intuitive argument which when formalized becomes the principle of mathematical induction:

Theorem: First Principle of Finite Induction:

Let S be a set of positive integers with the following properties:

The integer 1 belongs to S.
Whenever the integer k is in S, the next integer $k+1$ must also be in S.

Then, S is the set of all positive integers.

The proof of condition 1 is called basis step for the induction. The proof of 2 is called the induction step. The assumptions made in carrying out the induction step are known as induction hypotheses. The induction situation has been likened to an infinite row of dominoes all standing on edge and arranged in such a way that when one falls it knocks down the next in line. If either no domino is pushed over (that is, there is no basis for the induction), or if the spacing is too large (that is, the induction step fails), then the complete line will not fall.

So, also remember that the validity of the induction step does not necessarily depend on the truth of the statement that one is endeavouring to prove.

More later,

Nalin Pithwa.