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.

A math-magic sample from Mathologer

Posted by Nalin Pithwa

Some basics of RMO Number Theory: II. Linear Congruences

Posted by Nalin Pithwa

II. Linear congruences:

It is obvious that every integer is congruent (mod m) to exactly one of the numbers:

0, 1, 2, 3, 4, …, (m-1). ——- Note 1.

For, we can express the integer in the form $qm+r$ , where $0 \leq r <m$ , and then, it is congruent to $r {\pmod m}$ . Obviously, there are other sets of numbers, besides the set in Note 1, which have the same property, e.g., any integer is congruent (mod 5) to exactly one of the numbers 0, 1, -1, 2, -2. Any such set of numbers is said to constitute a complete set of residues to the modulus m. Another way of expressing the definition is to say that a complete set of residues (mod m) is any set of m numbers, no two of which are congruent to one another.

A linear congruence, by analogy with a linear equation in elementary algebra, means a congruence of the form

$ax \equiv b {\pmod m}$ —- Note 2.

It is an important fact that any such congruence is soluble for x, provided that a is relatively prime to m. The simplest way of proving this is to observe that if x runs through the numbers of a complete set of residues, then the corresponding values of ax also constitute a complete set of residues. For there are m of these numbers, and no two of them are congruent, since $ax_{1} \equiv ax_{2} {\pmod m}$ would involve $x_{1} \equiv x_{2} {\pmod m}$ , by the cancellation of the factor a (permissible since a is relatively prime to m). Since the numbers ax form a complete set of residues, there will be exactly one of them congruent to the given number b.

As an example, consider the congruence $3x \equiv 5 {\pmod {11}}$ ,

If we give x the values 0, 1, 2, …, 10 (a complete set of residues to the modulus 11), 3x takes the values 0, 3, 6, …30. These form another complete set of residues (mod 11), and in fact, they are congruent respectively to

0, 3, 6, 9, 1, 4, 7, 10, 2, 5, 8.

The value 5 occurs when $x=9$ , and so $x=9$ is a solution of the congruence. Naturally, any number congruent to 9 (mod 11) will also satisfy the congruence; but, nevertheless, we say that the congruence has one solution, meaning that there is one solution in any complete set of residues. In other words, all solutions are mutually congruent. The same applies to the general congruence (Note 2); such a congruence (provided that a is relatively prime to m) is precisely equivalent to the congruence $x \equiv x_{0} {\pmod m}$ , where $x_{0}$ is one particular solution.

There is another way of looking at the linear congruence (in note 2). It is equivalent to the equation $ax = b + my$ , or $ax - my =b$ . It can be proved that such a linear diophantine equation is soluble for x and y if a and m are relatively prime, and that fact provides another proof of the existence of a solution of linear congruence. But, the proof given above is simpler, and illustrates the advant4ages gained by using the congruence notation.

The fact that the congruence (in note 2) has a unique solution, in the sense explained above, suggests that one may use this solution as an interpretation for the fraction $\frac{b}{a}$ to the modulus m. When we do this, we obtain an arithmetic (mod m) in which addition, subtraction and multiplication are always possible, and division is also possible if the divisor is relatively prime to m. In this arithmetic there are only a finite number of essentially distinct numbers, namely m of them, since two numbers which are mutually congruent (mod m) are treated as the same. If we take the modulus m to be 11, as an illustration, a few examples of “arithmetic mod 11” are :

$5 + 7 \equiv 1$ ; $5 \times 6 \equiv 8$ ; $\frac{5}{3} \equiv 9 \equiv -2$ .

Any relation connecting integers or fractions in the ordinary sense remains true when interpreted in this arithmetic. For example, the relation $\frac{1}{2} + \frac{2}{3} = \frac{7}{6}$

becomes (mod 11)

$6 + 8 \equiv 3$ ,

because the solution of $2x \equiv 1$ is $x \equiv 6$ , that of $3x \equiv 2$ is $x \equiv 8$ , and that of $6x \equiv 7$ is $x \equiv 3$ . Naturally the interpretation given to a fraction depends on the modulus, for instance $\frac{2}{3} = 8 {\pmod 11}$ , but $\frac{2}{3} \equiv 3 {\pmod 7}$ . The only limitation on such calculations is that just mentioned, namely that the denominator of any fraction must be relatively prime to the modulus. If the modulus is a prime (as in the above examples with 11), the limitation takes the very simple form that the denominator must not be congruent to 0 (mod m), and this is exactly analogous to the limitation in ordinary arithmetic that the denominator must not be equal to 0. We will say more about this later.

Reference: The Higher Arithmetic, H. Davenport, 8th edition.

Shared for my students/readers who love to read expository articles….

Regards,

Nalin Pithwa.

Some Basics for RMO Number Theory: Congruences

Posted by Nalin Pithwa

I. The congruence notation:

It often happens that for the purposes of a particular calculation, two numbers which differ by a multiple of some fixed number are equivalent, in the sense that they produce the same result. For example, the value of $(-1)^{n}$ depends only on whether n is odd or even, so that two values of n which differ by a multiple of 2 give the same result. Or again, if we are concerned only with the last digit of a number, then for that purpose two numbers which differ by a multiple of 10 are effectively the same.

The congruence notation, introduced by Gauss, serves to express in a convenient form the fact that the two integers a and b differ by a multiple of a fixed natural number m. We say that a is congruent to b with respect to the modulus m, or in symbols,

$a \equiv b {\pmod m}$

The meaning of this, then, is simply that $a-b$ is divisible by m. The notation facilitates calculations in which numbers differing by a multiple of m are effectively the same, by stressing the analogy between congruence and equality. Congruence, in fact, means “equality except for the addition of some multiple of m”.

A few examples of valid congruences are :

$63 \equiv 0 {\pmod 3}$ ; $7 \equiv -1 {\pmod 8}$ ; $5^{2} \equiv -1 {\pmod {13}}$

A congruence to the modulus 1 is always valid, whatever the two numbers may be, since every number is a multiple of 1. Two numbers are congruent with respect to the modulus 2 if they are of the same parity, that is, both even or both odd.

Two congruences can be added, subtracted or multiplied together, in just the same way as two equations, provided all the congruences have the same modulus. If

$a \equiv \alpha {\pmod m}$ and $b \equiv \beta {\pmod m}$

then:

$a + b \equiv {\alpha + \beta} {\pmod m}$

$a - b \equiv {\alpha - \beta}{\pmod m}$

$ab \equiv {\alpha\beta} {\pmod m}$

The first two of these statements are immediate: for example, $(a+b) - (\alpha + \beta)$ is a multiple of m because $a- \alpha$ and $b - \beta$ are both multiples of m. The third is not quite so immediate because $ab - \alpha \beta = (a-\alpha)b$ , and $a - \alpha$ is a multiple of m. Next, $ab \equiv \alpha \beta$ , for a similar reason. Hence, $ab \equiv {\alpha \beta} {\pmod m}$ .

A congruence can always be multiplied throughout by any integer; if $a \equiv {\alpha} {\pmod m}$ the10n $ka \equiv {k\alpha} {\pmod m}$ . Indeed this is a special case of the third result above, where $b$ and $\beta$ are both k. But, it is not always legitimate to cancel a factor from a congruence. For example, $42 \equiv 12 {\pmod 10}$ , but it is not permissible to cancel the factor 6 from the numbers 42 and 12, since this would give the false result $7 \equiv 2 {\pmod 10}$ . The reason is obvious: the first congruence states that $42-12$ is a multiple of 10, but this does not imply that $\frac{1}{6}(42-12)$ is a multiple of 10. The cancellation of a factor from a congruence is legitimate if the factor is relatively prime to the modulus. For, let the given congruence be $ax \equiv ay {\pmod m}$ , where is the factor to be cancelled, and we suppose that a is relatively prime to m. The congruence states that $a(x-y)$ is divisible by m, and hence, $(x-y)$ is divisible by m.

An illustration of the use of congruences is provided by the well-known rules for the divisibility of a number by 3 or 9 or 11. The usual representation of a number n by digits in the scale of 10 is really a representation of n in the form

$n = a + 10b + 100c + \ldots$

where a, b, c, … are the digits of the number, read from right to left, so that a is the number of units, b the number of tens, and so on. Since $10 \equiv 1 {\pmod 9}$ , we have also $10^{2} \equiv 1 {\pmod 9}$ , and $10^3 \equiv 1 {\pmod 9}$ , and so on. Hence, it follows from the above representation of n that

$n \equiv {a+b+c+\ldots} {\pmod 9}$

In other words, any number n differs from the sum of its digits by a multiple of 9, and in particular n is divisible by 9 if and only if the sum of its digits is divisible by 9. The same applies with 3 in place of 9 throughout.

The rule for 11 is based on the fact that $10 \equiv -1 {\pmod 11}$ so that $10^2 \equiv {+1} {\pmod 11}$ , and so on. Hence,

$n \equiv {a-b+c- \ldots} {\pmod 11}$

It follows that n is divisible by 11 if and only if $a-b+c-\ldots$ is divisible by 11. For example, to test the divisibility of 958 by 11 we form 1-8+5-9, or -11. Since this is divisible by 11, so is 9581.

Ref: The Higher Arithmetic by H. Davenport, Eighth Edition, Cambridge University Press.

Cheers,

Nalin Pithwa.

Pre RMO (PRMO) practice questions, specially selected: PRMO 2018

Posted by Nalin Pithwa

The following set of problems tinkers, kindles some basic mathematical concepts as well as algebraic manipulations, so I suggest you try them out:

Try to decide by yourself which set of points are defined by these relations:

(a) $|x| = |y|$

(b) $\frac{x}{|x|} = \frac{y}{|y|}$

(d) $[x] = [y]$ .

Note: The symbol $[x]$ denotes the whole part of the number x, that is, the largest whole number not exceeding x. For example, $[3.5] = 3$ , $[5] = 5$ , $[-2.5] = -3$ .